Constructing levels in arrangements and higher order Voronoi diagrams

We give simple randomized incremental algorithms for computing the less than or equal to k-level in an arrangement of n lines in the plane or in an arrangement of n planes in R-3. The expected running time of our algorithms is O(nk + n alpha(n)logn) for the planar case and O(nk(2) + nlog(3)n) for the three-dimensional case. Both bounds are optimal unless k is very small. The algorithm generalizes to computing the less than or equal to k-level in an arrangement of discs or x-monotone Jordan curves in the plane. Our approach can also compute the k-level; this yields a randomized algorithm for computing the order-k Voronoi diagram of n points in the plane in expected time O(k(n - k) logn + nlog(3)n).
Publisher
SIAM PUBLICATIONS
Issue Date
1998-06
Language
ENG
Keywords

COMPUTATIONAL GEOMETRY; K-SETS; ALGORITHM; QUERIES

Citation

SIAM JOURNAL ON COMPUTING, v.27, no.3, pp.654 - 667

ISSN
0097-5397
DOI
10.1137/S0097539795281840
URI
http://hdl.handle.net/10203/318
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
1995-06.pdf(248.36 kB)Download
  • Hit : 606
  • Download : 370
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 44 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0