Abstract | ||
---|---|---|
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In linear space, and after O(n log n) preprocessing time, our solution maintains the view at a cost of O(log n) amortized time (resp. O(log(2) n) worst case time) for each change. Our algorithm can also be used to maintain the set of points sorted according to their distance to q. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1142/S0218195907002343 | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | DocType | Volume |
visibility, dynamic data structures | Journal | 17 |
Issue | ISSN | Citations |
4 | 0218-1959 | 2 |
PageRank | References | Authors |
0.41 | 5 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Olivier Devillers | 1 | 788 | 70.63 |
Vida Dujmovic | 2 | 416 | 43.34 |
Hazel Everett | 3 | 296 | 29.68 |
Samuel Hornus | 4 | 166 | 12.52 |
Sue Whitesides | 5 | 1449 | 197.63 |
Stephen K. Wismath | 6 | 387 | 32.61 |