TY - JOUR
TI - Some problems on discrete geometry and combinatorics
DO - https://doi.org/doi:10.7282/T3P55M3Q
PY - 2012
AB - Let 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.
KW - Computer Science
KW - Combinatorial analysis
KW - Discrete geometry
KW - Partitions (Mathematics)
LA - eng
ER -