RUcore Resource Object
RUcore Resource Object
PDF-1(762.55 KB)
TitleSome problems on discrete geometry and combinatorics
NameWang, Lei (author), Szegedy, Mario (chair), Steiger, William (co-chair), Kalantari, Bahman (internal member), Aronov, Boris (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2012-01
Date Created2012
SubjectComputer Science,
Combinatorial analysis,
Discrete geometry,
Partitions (Mathematics)
DescriptionLet K be a convex body in the plane. It is known that K can never be partitioned into seven regions of equal area by three non-concurrent lines. We will be concerned with a partition of K by three non-concurrent lines such that the ratio of the area of smallest region to the area of biggest region is maximum. We call this an optimal balanced partition at K. We show that the best possible ratio is achieved when K is a triangle and we characterize the optimal balanced partition in this case. We conjecture that the condition holds for optimal balanced partitions of all convex bodies but can only prove a weaker result. In the second part of the thesis, we switch to the zigzag problem. We are given a set of n points in R² and seek the minimum number of line segments required for a polygonal chain (or a simple polygonal chain) to traverse all the points. We show an n/2 + O(n/log{n}) upper bound if self-intersection is allowed and an n - [n-2/8] upper bound if self-intersection is not allowed. The third part of this thesis is about finding the optimally balanced forward degree sequence of a graph. The final part studies the optimal solutions for some variants of the Towers of Hanoi problem.
NotePh. D.
NoteIncludes bibliographical references
NoteIncludes vita
Noteby Lei Wang
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000064188
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.