Abstract
Let S be a set of n non-intersecting convex objects in the plane. A view of S from a given viewpoint p is the circular sequence of objets intersected by a semi-infinite line rotating continuously around the viewpoint p. We show how to preprocess the set S in time O(n 2 · α(n)) where α(n) is a pseudo-inverse of Ackermann's function, so that the view from a given point in the plane can be computed in time O(n · 2α(n)). Then we show how, with the same preprocessing time, the view can be maintained in O(log n) time per change while advancing the viewpoint along a given connected curve lying in the complement of the convex hull of S. Both algorithms use O(n 2) storage. In the process we show how to reduce by a log n factor the preprocessing time of the ray-shooting problem and we investigate a preprocessing version of the edge visibility problem. This work also serves to demonstrate that the geometric duality between the plane and the set of oriented straight lines of the plane is a “good” framework in dealing with objects more general then the classical points and segments which we usually meet in the context of computational geometry.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Pankaj K. Agarwal. Intersection and Decomposition Algorithms for Arrangements of Curves in the Plane. Technical Report Robotics Report No. 207, New York University Courant Institute of Mathematical Sciences, August 1989.
Bernard Chazelle and Leonidas J. Guibas. Visibility and Intersection Problems in Plane Geometry. Technical Report CS-TR-167-88, Princeton University Departement of Computer Science, June 1988.
Bernard Chazelle. Filtering search: a new approach to query-answering. SIAM J. Comput., 15(3):703–724, august 1986.
Driscoll, Sarnak, Sleator, and Tarjan. Making data structures persitents. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 669–679, May 1986.
H. ElGindy and D. Avis. A linear algorithm for computing the visibility polygon from a point. J.Algorithms, 2:186–197, 1981.
Edelsbrunner, Guibas, Pach, Pollack, Seidel, and Sharir. Arrangements of curves in the plane — topology, combinatorics and algorithms. In ICALP, pages 214–229, Springer-Verlag, 1988.
H. ElGindy. Hierarchical decomposition of polygon with applications. PhD thesis, NcGill Univ., 1985.
Herbert Edelsbrunner, Mark H. Overmars, and Derick Wood. Graphics in flatland: a case study. Advances in Computing Research, 1:35–59, 1983.
L.J. Guibas, J. Hersberger, D. Leven, M. Sharir, and R.E. Tarjan. Linear time algorithms for visibility and shortest path problems inside simple polygons. In Proceedings of the Second Annual ACM Symposium on Computational Geometry, pages 1–13, 1986.
H. Edelsbrunner, D.G. Kirkpatrick, and H.A. Maurer. Polygonal intersection searching. Information processing letters, 14:83–91, 1982.
David Kirkpatrick. Optimal search in planar subdivision. SIAM J. Comput., 12(1):28–35, February 1983.
D.T. Lee and A.K. Lin. Computing visibility polygon from an edge. Comput. Vision, Graphics, and Image Proc., 34:1–19, 1986a.
M. McKenna. Worst-case optimal hidden-surface removal. ACM Trans. on graphics, 6:19–28, January 1987.
J.-M. Moreau. A simple linear algorithm for polygon visibility. In ACM Siggraph France, editor, proceedings of first annual Conference on Computer Graphics in Paris, PIXIM 88, pages 151–161, 1988.
Joseph O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987.
Harry Plantinga and Charles Dyer. The Aspect Representation. Technical Report 683, University of Wisconsin-Madison, January 1987.
L.A. Santaló. Integral Geometry and Geometric Probability. Addison-Wesley, 1967.
Subhash Suri and Joseph O'Rourke. Worst-case optimal algorithms for constructing visibility polygons with holes. In Proceedings of the second ACM Symposium on Computational Geometry, pages 14–23, 1986.
Herbert Solomon. Geometric Probability. Society for Industrial and Applied Mathematics, 1978.
Neil Sarnak and Robert E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29, July 1986.
Robert E. Tarjan and Christopher J. Van Wyk. An O(n log log n)-time algorithm for triangulating a simple polygon. Siam J. Comput., 1:143–178, february 1988.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pocchiola, M. (1990). Graphics in flatland revisited. In: Gilbert, J.R., Karlsson, R. (eds) SWAT 90. SWAT 1990. Lecture Notes in Computer Science, vol 447. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52846-6_80
Download citation
DOI: https://doi.org/10.1007/3-540-52846-6_80
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-52846-3
Online ISBN: 978-3-540-47164-6
eBook Packages: Springer Book Archive