Topics in combinatorial and computational geometry
Edgar A. Ramos · 1995
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 $\LF 11n/6 \RF +1$ for the number of extreme triples of $n$ points in the plane, almost matching a known lower bound $\LF 11n/6 \RF$; (2) we determine some bounds for the smallest dimension $d=\Delta(j,k)$ such that for any $j$ mass distributions in $\R d$, there are $k$ hyperplanes so that each orthant contains a fraction $1/2^k$ of each of the masses; it is easily shown that $j(2^k-1)/k\leq\Delta(j,k)\leq j2^{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, $\XX \subseteq 2^B$, which has some nice topological properties, such that the inclusion-exclusion relation $\measure{\union{B}} = \sum_{\simplex \in 2^B-\{\emptyset\}} (-1)^{\card{\simplex}-1} \measure{\bigcap \simplex}$ holds when $\XX$ is substituted for $2^B$. In the second part, using geometric sampling techniques, we give algorithms for three similar problems: (4) Computing the intersection of halfspaces in $\R 3$; (5) computing the intersection of balls of equal radius in $\R 3$; and (6) computing the Voronoi diagram of line segments in $\R 2$; in each case we obtain a deterministic parallel algorithm for the EREW PRAM model that runs in time $O(\log^2 n)$ and uses work $O(n\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\log^2 n)$). Using the parallel algorithm for ball intersection, one obtains (7) a sequential deterministic algorithm for computing the diameter of a point set in $\R 3$ that runs in time $O(n\log^3 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^2 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^2(n)\log n)$ where $\alpha(n)$ is a very slowly growing function.