Home
Resource
Partitioning problems in discrete and computational geometry
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(599.19 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Zhao, Jihui. Partitioning problems in discrete and computational geometry. Retrieved from https://doi.org/doi:10.7282/T3X34XM8

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitlePartitioning problems in discrete and computational geometry
NameZhao, Jihui (author); Steiger, William (chair); Szegedy, Mario (internal member); Kalantari, Bahman (internal member); Bárány, Imre (outside member); Rutgers University; Graduate School - New Brunswick
Date Created
Other Date2010-01 (degree)
SubjectComputer Science, Discrete geometry, Geometry--Data processing
Extentviii, 65 p. : ill.
DescriptionMany interesting problems in Discrete and Computational Geometry involve partitioning. A main question is whether a given set, or sets, may be separated into parts satisfying certain properties. Sometime we also need to find an efficient way to do it - in other words an algorithm. In this thesis, we discuss several of problems and results of this kind.
First we give a combinatorial proof of the existence and the uniqueness of the generalized ham-sandwich cut for well separated point sets in R^d, that have the weak general position property. The combinatorial proof allows us to derive an O(n(log n)^d−3) running time algorithm to find a generalized cut for d given well separated point sets in R^d.
A second problem concerns the 6-way partition of a given convex set in R^2 using 3 lines. We reopen an old question and show that when the direction of one line is fixed, there is unique partition such that 6 regions have the same area.
In the Voronoi game two players A and B each play n points in a compact set S in R^d. They obtain scores equal to the total volume of the Voronoi cells of their points. There are one round and alternating versions of the game. We give the player A's best strategy to minimize the area of player B's one(first) Voronoi cell.
NotePh.D.
NoteIncludes bibliographical references (p. 62-64)
Noteby Jihui Zhao
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3X34XM8
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