Computing the visibility polygon using few variables

DOI10.1007/978-3-642-25591-5_9MaRDI QIDQ3104601zbMATH OpenOpenAlexFDO

Authors Stefan Langerman, Rodrigo I. Silveira, Luis Barba, Matias Korman

Publication date 16 December 2011

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.3584

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We present several algorithms for computing the visibility polygon of a simple polygon $P$ from a viewpoint inside the polygon, when the polygon resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in $O(nRout)$ time, where $Rout$ denotes the number of reflex vertices of $P$ that are part of the output. The next two algorithms use $O(logRin)$ variables, and output the visibility polygon in $O(nlogRin)$ randomized expected time or $O(nlo{g}^{2}Rin)$ deterministic time, where $Rin$ is the number of reflex vertices of $P$.

Recommendations

• Computing a visibility polygon using few variables
• A space-time trade-off for computing the visibility polygon in the multi-pass model
• Computing the visibility polygon from an edge
• Time-space trade-off for finding the k-visibility region of a point in a polygon
• scientific article; zbMATH DE number 4043246

Cited in

(8)

• A time-space trade-off for computing the k-visibility region of a point in a polygon
• Memory-constrained algorithms for simple polygons
• Time-space trade-off for finding the k-visibility region of a point in a polygon
• Computing the visibility polygon from an edge
• Reprint of: Memory-constrained algorithms for simple polygons
• Computing a visibility polygon using few variables
• Computing the visibility graph of points within a polygon
• A space-time trade-off for computing the visibility polygon in the multi-pass model

This page was built for publication: Computing the visibility polygon using few variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3104601)