×

Maintaining visibility information of planar point sets with a moving viewpoint. (English) Zbl 1145.65011

The authors present the first solution to the moving viewpoint query problem among points in 2D with provable worst-case and amortized complexity. More precisely, given a set of \(n\) points in the plane, they 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 a linear space, and after \({\mathcal O}(n\log n)\) preprocessing time, the solution maintains the view at cost of \({\mathcal O}(\log n)\) amortized time (respectively, \({\mathcal O}(\log^2 n)\) worst case time) for each change. The algorithm presented can also be used to maintain the set of points sorted according to their distance to \(q\).

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/0022-0000(89)90038-X · Zbl 0676.68013
[2] DOI: 10.1016/0022-0000(81)90012-X · Zbl 0474.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.