Files in this item



application/pdf9624467.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Topics in combinatorial and computational geometry
Author(s):Ramos, Edgar Arturo
Doctoral Committee Chair(s):Edelsbrunner, Herbert
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract: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 $\mu(\cup B) = \Sigma \sb{\sigma\in 2\sp{B} - \{\phi\}}(-1)\sp{\rm card\ \sigma -1}\mu(\cap\sigma)$ 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\alpha\sp2(n)\ \log\ n)$ where $\alpha(n)$ is a very slowly growing function.
Issue Date:1995
Rights Information:Copyright 1995 Ramos, Edgar Arturo
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9624467
OCLC Identifier:(UMI)AAI9624467

This item appears in the following Collection(s)

Item Statistics