DC Field | Value | Language |
---|---|---|
dc.contributor.author | Agarwal, PK | ko |
dc.contributor.author | de Berg, M | ko |
dc.contributor.author | Matousek, J | ko |
dc.contributor.author | Cheong, Otfried | ko |
dc.date.accessioned | 2007-05-25 | - |
dc.date.available | 2007-05-25 | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 1998-06 | - |
dc.identifier.citation | SIAM JOURNAL ON COMPUTING, v.27, no.3, pp.654 - 667 | - |
dc.identifier.issn | 0097-5397 | - |
dc.identifier.uri | http://hdl.handle.net/10203/318 | - |
dc.description.abstract | 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). | - |
dc.description.sponsorship | Work on this paper by P.A. has been supported by National Science Foundation Grant CCR-93-01259 and an NYI award. M.d.B and O.S. acknowledge support by the Netherlands's Organization for Scientific Research (NWO) and partial support by ESPRIT Basic Research Action No.7141 (project ALCOM II: Algorithms and Complexity). Work by J.M. was supported by Charles University Grant No.351 by Czech Republic Grant GACR 201/93/2167 and by EC Cooperative Action IC-1000 (project ALTEC: Algorithms for Future Technologies). Part of this research was done when P.A. and O.S. visited Charles University, and when P.A. visited Utrecht University. These visits were supported by Charles University and NWO. | en |
dc.language | English | - |
dc.language.iso | en | en |
dc.publisher | SIAM PUBLICATIONS | - |
dc.subject | COMPUTATIONAL GEOMETRY | - |
dc.subject | K-SETS | - |
dc.subject | ALGORITHM | - |
dc.subject | QUERIES | - |
dc.title | Constructing levels in arrangements and higher order Voronoi diagrams | - |
dc.type | Article | - |
dc.identifier.wosid | 000073559600004 | - |
dc.identifier.scopusid | 2-s2.0-0001698164 | - |
dc.type.rims | ART | - |
dc.citation.volume | 27 | - |
dc.citation.issue | 3 | - |
dc.citation.beginningpage | 654 | - |
dc.citation.endingpage | 667 | - |
dc.citation.publicationname | SIAM JOURNAL ON COMPUTING | - |
dc.identifier.doi | 10.1137/S0097539795281840 | - |
dc.embargo.liftdate | 9999-12-31 | - |
dc.embargo.terms | 9999-12-31 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | Agarwal, PK | - |
dc.contributor.nonIdAuthor | de Berg, M | - |
dc.contributor.nonIdAuthor | Matousek, J | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | arrangements | - |
dc.subject.keywordAuthor | random sampling | - |
dc.subject.keywordAuthor | Voronoi diagrams | - |
dc.subject.keywordPlus | COMPUTATIONAL GEOMETRY | - |
dc.subject.keywordPlus | K-SETS | - |
dc.subject.keywordPlus | ALGORITHM | - |
dc.subject.keywordPlus | QUERIES | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.