Topics in combinatorial and computational geometry

This thesis consists of two parts dealing with combinatorial and computational problems in geometry, respectively. In the first part three independent problems are considered: (1) We determine an upper bound $\lfloor 11n/6\rfloor$ + 1 for the number of extreme triples of n points in the plane, almost matching a known lower bound $\lfloor 11n/6\rfloor$; (2) we determine some bounds for the smallest dimension $d = \Delta(j,k)$ such that for any j mass distributions in $\IR\sp{d}$, there are k hyperplanes so that each orthant contains a fraction 1/2$\sp{k}$ of each of the masses; it is easily shown that $j(2\sp{k}-1)/k \le \Delta(j,k)\le j2\sp{k-1}$; we believe the lower bound is tight, but can only prove it in a few cases (as a tool we prove a Borsuk-Ulam theorem on a product of balls, which is of independent interest); (3) for a collection B of pseudo-disks in the plane, we show the existence of a two-dimensional abstract simplicial complex, $\chi \subseteq 2\sp{B}$, which has some nice topological properties, such that the inclusion-exclusion relation μ(\cup B) = \Sigma \sb{σ\in 2\sp{B} - \{\phi\}}(-1)\sp{\rm card σ -1}μ(\capσ) holds when $\chi$ is substituted for 2$\sp{B}$. In the second part, using geometric sampling techniques, we give algorithms for three similar problems: (4) Computing the intersection of halfspaces in $\IR\sp3$; (5) computing the intersection of balls of equal radius in $\IR\sp3$; and (6) computing the Voronoi diagram of line segments in $\IR\sp2$; in each case we obtain a deterministic parallel algorithm for the EREW PRAM model that runs in time O({\rm log}\sp2 n) and uses work O(n {\rm log} n) for a problem of size n (for ball intersection this is also the first optimal deterministic and sequential algorithm, using the Dobkin-Kirkpatrick decomposition, we can only achieve time O(n {\rm log}\sp2 n)). Using the parallel algorithm for ball intersection, one obtains (7) a sequential deterministic algorithm for computing the diameter of a point set in $\IR\sp3$ that runs in time O(n {\rm log}\sp3 n). Using also geometric sampling techniques, (8) we describe an algorithm for computing the arrangement of n segments in the plane in time $O(\log\sp2 n)$ and using work O(n \log n + k) where k is the number of pairwise intersections, also in the EREW PRAM model (sequentially this results in an algorithm that outputs all the intersections in optimal time using O(n) space); and (9) assuming that certain sampling result can be derandomized in polynomial time, we describe a sequential algorithm for computing one face in an arrangement of segments that runs in time O(nα\sp2(n) \log n) where α(n) is a very slowly growing function.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Ramos, Edgar Arturo

Contributors dc:contributor

• Edelsbrunner, Herbert

• Computer Science

Statement dc:rights

• Copyright 1995 Ramos, Edgar Arturo

Language dc:language

eng

Identifier

AAI9624467
(UMI)AAI9624467

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/22868