### Delaunay triangulations in $\textit{O}(sort(\textit{n}))$ time and moreDelaunay triangulations in $\textit{O}(sort(\textit{n}))$ time and more

Access Restriction
Subscribed

 Author Buchin, Kevin ♦ Mulzer, Wolfgang Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2011 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Convex hull ♦ Delaunay triangulation ♦ Word RAM Abstract We present several results about Delaunay triangulations (DTs) and convex hulls in transdichotomous and hereditary settings: (i) the DT of a planar point set can be computed in expected time $\textit{O}(sort(\textit{n}))$ on a word RAM, where $sort(\textit{n})$ is the time to sort $\textit{n}$ numbers. We assume that the word RAM supports the $\textit{shuffle}$ operation in constant time; (ii) if we know the ordering of a planar point set in $\textit{x}-$ and in $\textit{y}-direction,$ its DT can be found by a randomized algebraic computation tree of expected $\textit{linear}$ depth; (iii) given a universe $\textit{U}$ of points in the plane, we construct a data structure $\textit{D}$ for Delaunay queries: for any $\textit{P}$ ⊆ $\textit{U},$ $\textit{D}$ can find the DT of $\textit{P}$ in expected time $\textit{O}(|\textit{P}|$ log log $|\textit{U}|);$ (iv) given a universe $\textit{U}$ of points in 3-space in general convex position, there is a data structure $\textit{D}$ for convex hull queries: for any $\textit{P}$ ⊆ $\textit{U},$ $\textit{D}$ can find the convex hull of $\textit{P}$ in expected time $\textit{O}(|\textit{P}|$ (log log $|U|)^{2});$ (v) given a convex polytope in 3-space with $\textit{n}$ vertices which are colored with χ ≥ 2 colors, we can split it into the convex hulls of the individual color classes in expected time $\textit{O}(\textit{n}$ (log log $n)^{2}).$ The results (i)--(iii) generalize to higher dimensions, where the expected running time now also depends on the complexity of the resulting DT. We need a wide range of techniques. Most prominently, we describe a reduction from DTs to nearest-neighbor graphs that relies on a new variant of randomized incremental constructions using $\textit{dependent}$ sampling. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2011-04-11 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 58 Issue Number 2 Page Count 27 Starting Page 1 Ending Page 27

#### Open content in new tab

Source: ACM Digital Library