Expanding Visibility Polygons by Mirrors

Please enable javascript in your browser.

This page was sent successfuly

Bookmark

108 viewed

گسترش چندضلعی های قابل دید با استفاده از اضلاع آینه ای

1546 Viewed

Type of Document: M.Sc. Thesis
Language: Farsi
Document No: 44166 (19)
University: Sharif University of Technology
Department: Computer Engineering
Advisor(s): Ghodsi, Mohammad
Abstract:
We consider extending the visibility polygon of a given point q inside a simple polygon by converting one or some of the edges to mirrors. It is known that the visibility polygon of a point inside a polygon in the presence of a mirror can be computed in linear time. We propose a linear time algorithm that checks whether a given segment inside a simple polygon is visible by a given point q via a mirror-edge, and finds all such edges. And we prove that finding edges to add exactly k unit squares to the visibility polygon of a query point q in most cases is NP-complete and its minimization is NP-hard. These cases contain single and muliple, either with secular or difuse reflections. Moreover, considering the same cases findig edges to add at least k unit squares with minimum number of mirror-edges is NP-hard, too. The mutiple reflections case of the specular version of the at least k problem, has been left open
Keywords:
Mirror ; Visibility Polygon ; Specular Reflection ; Diffuse Reflection ; Single Reflection ; Multiple Reflection