Expanding Visibility Polygons by Mirrors upto at least K units
share
We consider extending visibility polygon (VP) of a given point q (VP(q)), inside a simple polygon by converting some edges of to mirrors. We will show that several variations of the problem of finding mirror-edges to add at least k units of area to VP(q) are NP-complete, or NP-hard. Which k is a given value. We deal with both single and multiple reflecting mirrors, and also specular or diffuse types of reflections. In specular reflection, a single incoming direction is reflected into a single outgoing direction. In this paper diffuse reflection is regarded as reflecting lights at all possible angles from a given surface. The paper deals with finding mirror-edges to add at least k units of area to VP(q). In the case of specular type of reflections we only consider single reflections, and the multiple case is still open. Specular case of the problem is more tricky. We construct a simple polygon for every given instance of a 3-SAT problem. There are some specific spikes which are visible only by some particular mirror-edges. Consequently, to have minimum number of mirror-edges it is required to choose only one of these mirrors to see a particular spike. There is a reduction polygon which contains a clause-gadget corresponding to every clause, and a variable-gadget corresponding to every variable. 3-SAT formula has n variables and m clauses, so the minimum number of mirrors required to add an area of at least k to V P(q) is l = 3m+n+1 if and only if the 3-SAT formula is satisfiable. This reduction works in these two cases: adding at least k vertex of to VP(q), and expanding VP(q) at least k units of area.
READ FULL TEXT