2026-09-19T23:45:42Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/22868 2023-07-10 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Edelsbrunner, Herbert Ramos, Edgar Arturo 2011-05-07T13:54:10Z 2011-05-07T13:54:10Z 10000-01-01 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 $\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. Made available in DSpace on 2011-05-07T13:54:10Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624467.pdf: 5930366 bytes, checksum: 19645fa8e1d97d1bac114b12d132e564 (MD5) Previous issue date: 1995 Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:00:34Z Item is restricted indefinitely. Restriction data tranferred 2014-07-01T11:28:39-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission ETDs are only available to UIUC Users without author permission U of I Only AAI9624467 (UMI)AAI9624467 http://hdl.handle.net/2142/22868 eng Copyright 1995 Ramos, Edgar Arturo Computer Science Topics in combinatorial and computational geometry text Computer Science Computer Science University of Illinois at Urbana-Champaign Dissertation Ph.D.