Access Restriction

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

   Open content in new tab
Source: ACM Digital Library