Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Convex Hull
convex polytope
Data Structure
delaunay triangulation
Generalized Convexity
Higher Dimensions
Nearest Neighbor Graph
Subscribe
Academic
Publications
Delaunay triangulations in O (sort( n )) time and more
Delaunay triangulations in O (sort( n )) time and more,10.1145/1944345.1944347,Journal of The ACM,Kevin Buchin,Wolfgang Mulzer
Edit
Delaunay triangulations in O (sort( n )) time and more
BibTex

RIS

RefWorks
Download
Kevin Buchin
,
Wolfgang Mulzer
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 O(sort(n)) on a word RAM, where sort(n) is the time to sort n numbers. We assume that the word RAM supports the shuffle operation in constant time; (ii) if we know the ordering of a planar point set in x and in ydirection, its DT can be found by a randomized algebraic computation tree of expected linear depth; (iii) given a universe U of points in the plane, we construct a
data structure
D for Delaunay queries: for any P ⊆ U, D can find the DT of P in expected time O(P log log U); (iv) given a universe U of points in 3space in general convex position, there is a
data structure
D for
convex hull
queries: for any P ⊆ U, D can find the
convex hull
of P in expected time O(P (log log U)2); (v) given a
convex polytope
in 3space with n vertices which are colored with χ ≥ 2 colors, we can split it into the convex hulls of the individual color classes in expected time O(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 nearestneighbor graphs that relies on a new variant of randomized incremental constructions using dependent sampling.
Journal:
Journal of The ACM  JACM
, vol. 58, no. 2, pp. 127, 2011
DOI:
10.1145/1944345.1944347
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
(
doi.acm.org
)
More »
References
(62)
Improved Parallel Integer Sorting without Concurrent Writing
(
Citations: 52
)
Susanne Albers
,
Torben Hagerup
Journal:
Information and Computation/information and Control  IANDC
, vol. 136, no. 1, pp. 2551, 1997
Complexity of Delaunay triangulation for points on lowerdimensional polyhedra
(
Citations: 14
)
Nina Amenta
,
Dominique Attali
,
Olivier Devillers
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 11061113, 2007
Incremental constructions con BRIO
(
Citations: 29
)
Nina Amenta
,
Sunghee Choi
,
Günter Rote
Conference:
Symposium on Computational Geometry  SOCG
, pp. 211219, 2003
Efficient Regular Data Structures and Algorithms for Location and Proximity Problems
(
Citations: 16
)
Arnon Amir
,
Alon Efrat
,
Piotr Indyk
,
Hanan Samet
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 160170, 1999
Sorting in linear time?
(
Citations: 88
)
Arne Andersson
,
Torben Hagerupt
,
Stefan Nilsson
,
Rajeev Raman
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 427436, 1995