Home
Resource
Some problems on discrete geometry and combinatorics
PDF
PDF format is widely accepted and good for printing.
Plug-in required
Some problems...(762.55 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Wang, Lei. Some problems on discrete geometry and combinatorics. Retrieved from https://doi.org/doi:10.7282/T3P55M3Q

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

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
Date Created2012
Other Date2012-01 (degree)
SubjectComputer Science, Combinatorial analysis, Discrete geometry, Partitions (Mathematics)
Extentvii, 74 p. : ill.
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, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3P55M3Q
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.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024