Computing a visibility polygon using few variables

Details Computing a visibility polygon using few variables Computing a visibility polygon using few variables

2011-11-15

arxiv.org/abs/1111.3584v1

Computer Science

Computational Geometry

11 pages. Full version of paper in Proceedings of ISAAC 2011

Scientific paper

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(n\Rout)$ time, where $\Rout$ denotes the number of reflex vertices of $P$ that are part of the output. The next two algorithms use $O(\log \Rin)$ variables, and output the visibility polygon in $O(n\log \Rin)$ randomized expected time or $O(n\log^2 \Rin)$ deterministic time, where $\Rin$ is the number of reflex vertices of $P$.

Affiliated with

Also associated with

No associations

Rating

Computing a visibility polygon using few variables does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing a visibility polygon using few variables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing a visibility polygon using few variables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-709807