Topics in combinatorial and computational geometry
Ramos, Edgar Arturo
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/22868
Description
Title
Topics in combinatorial and computational geometry
Author(s)
Ramos, Edgar Arturo
Issue Date
1995
Doctoral Committee Chair(s)
Edelsbrunner, Herbert
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
