WorksComputer Science
A Polynomial-Time Algorithm for Maximum Witness Set
Abstract
A witness set in a polygon is a set of points whose visibility regions are pairwise disjoint. Since no point of the polygon can see more than one witness, the cardinality of a witness set provides a lower bound on the minimum number of guards required to cover the polygon. Finding a maximum witness set is therefore a natural packing counterpart to the classical Art Gallery problem. While the latter is -complete, the computational complexity of finding a maximum witness set in a general simple polygon has remained open. In this paper, we present a polynomial-time algorithm for computing a maximum witness set in a simple polygon with vertices, of which are reflex, assuming that no three vertices are collinear. Our algorithm runs in time. Our approach exploits a tree structure induced by witness visibility regions and employs geometric dynamic programming over nested regions determined by visibility windows.
Introduction
Visibility-based optimization problems are among the central topics in computational geometry. The classical Art Gallery problem asks for a minimum set of guards whose visibility regions together cover a given polygon [10, 9]. Two points in a polygon are said to be visible to each other if the line segment lies entirely in . The visibility region of a point , denoted by , consists of all points of visible from .
A natural packing counterpart to the Art Gallery problem is the Witness Set problem, introduced by Amit, Mitchell, and Packer [2]. A point set is called a witness set if the visibility regions of its points are pairwise disjoint, that is, for every pair of distinct witnesses (see Figure 1 for an illustration). Equivalently, no point of the polygon can see more than one witness. Consequently, every guard set must contain at least guards, and hence the maximum cardinality of a witness set provides a lower bound on the minimum number of guards required to cover the polygon. Such lower bounds are particularly useful in exact art gallery algorithms, where matching lower and upper bounds certify the optimality of a guard configuration.
Despite this close connection, the two problems impose fundamentally different geometric requirements. While the Art Gallery problem seeks a minimum collection of visibility regions whose union covers the polygon, the Witness Set problem seeks a maximum collection of pairwise disjoint visibility regions. Moreover, the witness-set condition is stronger than requiring the selected points to be mutually invisible. Indeed, two witnesses must not only be invisible to each other, but there must be no point anywhere in the polygon that sees both. Thus, a witness set is also a hidden set, but the converse need not hold.
In this paper, we study the following optimization problem.
Maximum Witness Set. Input: A simple polygon with vertices. Output: A maximum-cardinality point set such that for every pair of distinct points .
We denote the maximum cardinality of a witness set in by . Unlike many classical packing problems, the candidates for a witness set are not given explicitly: witnesses may be placed anywhere in the polygon. Thus, even though the input polygon has finitely many vertices, the solution space is continuous and contains infinitely many possible witness configurations. The main challenge is to identify enough geometric structure to avoid searching this space explicitly.
Motivation and Related Work
The computational difficulty of geometric visibility problems is closely related to the continuous nature of their solution spaces. The Art Gallery problem is known to be NP-hard [12] and APX-hard [7]. In a major breakthrough, Abrahamsen, Adamaszek, and Miltzow [1] proved that the Art Gallery problem is -complete, even for polygons with integer coordinates. Consequently, it does not belong to NP unless . In particular, this rules out a polynomial-size certificate consisting of polynomial-bit rational guard coordinates unless these complexity classes coincide.
The packing nature of the Witness Set problem suggests a potentially different algorithmic behavior. A witness set requires its visibility regions to be mutually disjoint, imposing a strong separation condition absent from the guarding problem. Although this separation requirement makes the feasibility condition more restrictive, it may also provide additional geometric structure that can be exploited algorithmically. In particular, one may hope to decompose a witness set into smaller collections whose visibility regions are separated by suitable geometric boundaries.
Amit, Mitchell, and Packer [2] introduced visibility-independent witness points in the context of computing lower bounds for polygon guarding. They used large witness sets to assess guarding heuristics and to certify optimality when the resulting lower bounds matched the sizes of guard sets. This established witness sets as a useful tool in the study of exact guarding problems. Nevertheless, the algorithmic problem of finding a maximum witness set remained much less understood than its covering counterpart.
Early exact results were obtained for special polygon classes. Daescu, Friedrichs, Malik, Polishchuk, and Schmidt [5] developed a linear-time algorithm for guarding monotone

Figure 1. A simple polygon with a witness set . The colored regions are the visibility regions of the witnesses; they are pairwise disjoint.
mountains and showed that the minimum guard number equals the maximum witness number for this class. More recently, Das et al. [3, 4] studied the continuous Witness Set problem in monotone polygons. They obtained an exact algorithm with running time , where is the number of reflex vertices and is the desired witness-set size, together with a polynomial-time approximation scheme. They also gave a polynomial-time algorithm for the discrete version of the problem in simple polygons.
A further development is due to Das, Mondal, and Roy [6], who obtained polynomial-time algorithms for both the continuous and discrete versions of Witness Set in weak visibility polygons. Their continuous algorithm runs in time. These results exploit structural properties of weak visibility polygons, in which every point is visible from some point of a fixed boundary edge. However, arbitrary simple polygons need not possess such a distinguished edge or the associated geometric structure.
For general simple polygons, Jana et al. [11] established that the decision version of Witness Set belongs to both NP and XP. Their approach constructs a finite candidate set of size , for a computable function , and reduces the continuous problem to a discrete instance. This yields an exact algorithm whose running time is polynomial for every fixed value of , but whose exponent depends on . The same work also established NP-completeness of the discrete variant for rectilinear polygons with holes.
Thus, while the complexity of witness sets in several restricted classes of polygons has been investigated, the existence of a polynomial-time algorithm for arbitrary simple polygons has remained open. In particular, the parameter-dependent approach for general simple polygons does not resolve the problem when the size of an optimal witness set is unrestricted.
This motivates the central question of our work:
Can the geometric separation of visibility regions be exploited to compute a maximum witness set in a general simple polygon in polynomial time?
Our approach answers this question in the real-RAM model by exploiting a recursive structure induced by witness sets. Rather than enumerating candidate witness configurations, we represent subproblems by suitably chosen geometric regions and combine their solutions using dynamic programming.
Our Results and Method
Our main result is a polynomial-time algorithm for computing a maximum witness set in a general simple polygon. We assume that no three vertices of the input polygon are collinear. Let be the number of vertices of the polygon and the number of its reflex vertices.
Theorem 1. For a simple polygon with vertices, of them reflex, and no three vertices on a line, a maximum witness set can be computed in time.
Our algorithm is based on a geometric dynamic programming approach. Its main insight is that the separation of visibility regions induces a recursive structure, allowing a witness set to be decomposed into smaller subproblems. We next outline the geometric ingredients that make this approach possible.
A tree structure induced by witness sets. Consider a witness set in a simple polygon . Since the visibility regions of distinct witnesses are disjoint, the regions not visible from any witness separate these visibility regions. The boundaries of visibility regions are partly determined by windows, which are segments extending from reflex vertices to the polygon boundary.
We establish a structural property showing that the visibility regions of the witnesses, together with the intervening non-visible components, induce a tree whose adjacencies are determined by these windows. Rooting this tree at a witness allows us to organize the remaining witnesses into subtrees. Each such subtree corresponds to a smaller geometric subproblem, separated from the rest of the configuration by an appropriate window.
Nested caps and compact subproblems. A window separates the polygon into two sides, one of which contains the corresponding witness. We call this side a cap. The visibility region of the witness lies entirely within its cap, and a cap may also contain the visibility regions of several other witnesses belonging to the same subtree.
The crucial geometric observation is that caps associated with the same reflex vertex and the same side are totally ordered by inclusion. Thus, among all caps of a fixed type supporting the same number of witnesses, it is sufficient to retain an extremal one. This nesting property provides the state compression underlying our dynamic programming algorithm.
Dynamic programming over caps. We associate a state with a triple , where denotes the number of witnesses, is a reflex vertex, and specifies one of the two sides associated with . The corresponding dynamic programming entry represents the smallest limiting cap of type that can support witnesses.
By the classical art gallery theorem, every witness set contains at most points. Consequently, the number of states is at most , which is polynomial in the input size.
To compute a state, we select a root witness and combine solutions to smaller subproblems. The caps containing these subproblems must be pairwise disjoint, lie inside the cap associated with the root, and avoid the root’s visibility region. We show that the relevant compatibility conditions can be expressed through boundary arcs of caps. This reduces the selection of compatible child subproblems to a weighted interval scheduling problem, with weights corresponding to the numbers of witnesses supported by the child caps.
Handling the continuous search space. A remaining difficulty is that a root witness can be placed anywhere inside the polygon. Consequently, even though the dynamic programming table has polynomially many states, each state initially involves infinitely many possible witness locations.
We overcome this difficulty by constructing a suitable arrangement of lines. The arrangement is determined by the polygon edges, lines through reflex vertices, and geometric regions associated with previously computed states. These lines partition the polygon into polynomially many cells.
The key property is that, within an open arrangement cell, the combinatorial information relevant to the dynamic programming recurrence remains unchanged. In particular, the available window types and the admissibility of previously computed subproblems are constant throughout the cell. Thus, a single representative point suffices to determine the feasibility of a state within that cell.
Moreover, the nesting of caps allows us to determine an extremal cap for each feasible cell by considering an appropriate extreme corner. Processing the states in increasing order of the number of witnesses yields the claimed polynomial-time algorithm.
Computing an optimal witness set. After the dynamic programming table has been constructed, the algorithm considers an unrestricted root witness and combines compatible previously computed subproblems. A final weighted interval scheduling computation determines the maximum number of witnesses that can be supported.
The extremal objects stored in the table may arise as limits of ordinary caps. The algorithm therefore records the geometric information needed to choose appropriate witness positions and recover an optimal solution.
The main advantage of our approach is that it avoids enumerating witness configurations. Instead, the tree structure of witness visibility regions provides a recursive decomposition, the nesting of caps permits a compact representation of subproblems, and line arrangements together with weighted interval scheduling allow the resulting dynamic programming recurrence to be evaluated efficiently. Our running-time bound is stated in the real-RAM model, in which arithmetic operations and comparisons involving real numbers are assumed to take constant time.
Organization. Section 2 introduces the necessary geometric definitions and notation. We then establish the tree structure induced by witness sets and the properties of windows and caps. In section 4, we develop the dynamic programming formulation. Finally, section 5 presents the algorithm, proves its correctness, and analyzes its running time.
Preliminaries
Definition 2. A polygon is a closed region in the plane bounded by a finite sequence of non-intersecting line segments, called its edges. The endpoints of these edges are its vertices. A polygon with holes is a polygon whose boundary consists of more than one disjoint simple cycle: one outer boundary and one or more interior boundaries. A polygon is simple if it is neither self-intersecting nor contains holes.
For a polygon , we denote its boundary by and its interior by . A vertex of is convex if its interior angle is at most ; otherwise, it is reflex. Let and be the number of vertices and the reflex vertices of respectively. For a line segment , we denote its interior by and its boundary by .
Definition 3. Two points are visible to each other if the segment is contained entirely in . The visibility region of is . For a set , .
Definition 4. In a polygon , a finite point set is said to be a witness set of if for all distinct . A witness point is a point of . See Figure 1.
Lemma 5. Every witness set has at most points.
Proof. By Fisk’s proof of the art gallery theorem [8], some vertices see all of . Each of them sees at most one witness. □
Definition 6. Let . Suppose sees a reflex vertex , and the ray from through goes on into the interior of after . Define to be the boundary point on this ray such that it goes outside after . The segment is a window of .
For a point , let be a window of and be the two incident edges of . For , let be the path from to along such that lies in . For , let be the region bounded by the path and the line segment . Then, (since ) and exactly one of contains .
Definition 7. We call the contained side of if it contains , written , and the other region the pocket side of .
Definition 8. A point has type , for , if contains . We define the cap of associated with as and denote it by . We define its boundary arc , which is precisely . We also define the corresponding window of to be .
Remark 9. There are cases where both the pocket side and the contained side of a window of a point is not simple polygons. This happens when lies on the line joining two reflex vertices (both of which are visible from and lies on the same side of ) such that the pairs of edges of those reflex vertices lies on the either side of . Note that, in that case, is also not a simple polygon. See page 4-5 of [11] for detailed notion.
The following observation is immediate from the definition of a window.
Observation 10. For every window of a point , we have .
Definition 11. For two points , if , then lies in exactly one pocket side of for some window of . We call it a window of facing and denote it by .
Lemma 12. Let with . Put and . Then if and only if and are disjoint and lies on the pocket side of .
Proof. If the regions are disjoint, so are and . The region is connected, contains and , and misses , so it stays on the pocket side of . Conversely, two disjoint chords cut into two outer parts and a middle part. The hypotheses place and in different outer parts, and Observation 10 places their visibility regions there as well.
Witness Tree
Definition 13. For a witness set , define the graph with one node for each region , , and one node for each connected component of . Join two nodes if their regions meet along a window.
Remark 14.
For any two witnesses , their distance in is always even, since there is at least one connected component of between and .
For a node corresponding to , we simply use as shorthand notation.
Lemma 15. For a witness set , is a tree.
Proof. For each , the windows of lies in distinct rays from and no window contains . So all the windows of are disjoint. Windows of different witnesses lie in disjoint visibility regions, so they are disjoint. Let denote the collection of all windows of the points in . We cut along these windows one at a time. For each , we consider a graph with one node for each connected component of and there is an edge between two nodes if their corresponding components lie on either side of some , . Observe that, . Since is a chord, it divides the polygon into two parts, has two nodes which are connected by a single edge. So, is a tree. Now, assume that is a tree. Let lies on the component of . cuts into two parts and , so there is an edge between and in and hence is connected. Only one new edge has been introduced to and two new nodes replaced one old node. Thus since , and . So is a tree and hence is a tree by induction.
Lemma 16. Let be a reflex vertex with incident edges and . Let be the set of all caps associated with for , arising from the points of type . Then the elements of are totally ordered by inclusion.
Proof. Two windows that start at cannot cross elsewhere. The cap with the shorter boundary arc is therefore contained in the other one.
Observation 17. Let be a cap and be two points in such that , . Then any path between and must intersect .
Lemma 18. Let be two caps. Then the followings are true.
if and only if .
if and only if .
Proof. For (1), one direction holds because the arcs lie in the caps. For the reverse direction, observe that is precisely the closed region bounded by and . Since the endpoints of lies in and , and are also disjoint. Thus the regions bounded by and are disjoint. Hence .
Now, let . Then, . For the reverse direction, let . Since is the region bounded by the simple polygonal chain and the line segment , .
Definition 19. For a cap , define .
Lemma 20. For a point , we have if and only if .
Proof. Let . As , . If , then there exists such that sees which implies that , a contradiction. Thus . Conversely, let . Now since . So, using Observation 17, the visibility line segment intersects at (let). Thus , a contradiction.
Definition 21. A witness set is confined to a set if for all .
Lemma 22. Root at a witness point . For any other witness , let (a window of facing ) and let . Let be the set of witness points which are in the subtree rooted at . Then is confined to the cap . Let are distance two descendants of in . Then , , and for each .
Moreover, if is confined to a cap of the root , then .
Proof. The chord divides into two pieces one of which is and the other one is the pocket side of . Let . Clearly, is contained in exactly one of the pieces since , and is a connected region. Now, if is contained in the pocket side of , then and are in the same side of . which implies there is a path in from the root to which does not contain . This contradicts the tree structure of since lies in the subtree rooted at so the path from to must go through . Thus, and is confined to . Observe that, is the union of the regions descendant to and . Thus , since descendants of and are disjoint and . Now, lies on the pocket side of since . So, and . If is confined to a cap of , then is the union of the regions descendant to and . Hence, because is also the union of the regions descendant to and .
Observation 23. Let be a point and be a cap of . For , let be a cap such that the are pairwise disjoint, and there is a witness set of size confined to . Then is a witness set of size . Moreover, if each is contained in a cap of , then is confined to .
The Dynamic Programming
Definition 24. A state is a triple with , a reflex vertex and . A cap of works for if some witness set of size contains and is confined to the cap. For a state , we define . Let be the family of caps that work for and define .
Let . There are at most states since , is the number of reflex vertices and . Deleting a witness keeps a set confined. Hence, we have the following observation.
Observation 25. Let . If a cap works for , then also works for . Moreover, and .
Definition 26. Let be regular with a cap . A cap is called admissible for in if and . is called root-admissible for if .
Lemma 27. Let be a cap of , and let be a cap at some reflex vertex such that . Then if and only if .
Proof. We have . For the forward direction, let . Then, , since (using Lemma 18) and . Now, for the reverse direction, let . If is not contained in , there exists . Since is connected, there is a path between and . Now, and , so must intersect using Observation 17. Thus, , which is a contradiction.
Lemma 28. The cap works for if and only if there exist states satisfying the following properties for some .
, for each .
are pairwise disjoint and each is non-empty and admissible for in .
.
Clearly, for , the empty family is allowed since any cap of associated to works for .
Proof. For the forward direction, let works for . Let be a witness set confined to such that and . Now, we consider the tree rooted at . Let are the distance two descendants of . Let and . Let be the size of subtree of rooted at , and let be a reflex vertex and be such that . So, . Define for each . The conditions (1) and (3) are satisfied, since . Now, using Lemma 22, are pairwise disjoint, , and . Thus, condition (2) is also satisfied because for each .
For the reverse direction, let be a state and there are states satisfying the three conditions. Let be a witness set of size confined in , and , . Thus, using Observation 23, is a witness set of size confined in . So, works for as well as using Observation 25.
Remark 29. Suppose works for then there exist states satisfying the three properties of Lemma 28. Now, by Observation 25, we can always choose a family such that it satisfies the first two properties of Lemma 28 with the equality . We call such a family a child record of .
Algorithm for Finding Maximum Witness Set
Define for some state with . Let consists of the supporting lines of the edges of and be the set of lines through a reflex vertex and another vertex. Now, define to be the set of supporting lines of the edges of for each .
Definition 30. The arrangement of row , denoted by , is defined as . The lines of divide into convex regions, which we call cells. Let denote the set of all such cells contained in . The intersection of two distinct cells, if nonempty, lies entirely on their boundaries. For a cell , let be the arithmetic mean of all vertices of .
We have , , since there are at most states and has edges for . So, there are lines in . Now, the number of cells created by the lines in is . Thus, .
Lemma 31. Let and be two points in . Then the followings are true.
has type if and only if has type , i.e., the available types inside a cell remains same.
For an available type and for , is admissible for in if and only if is admissible for in .
Proof. (1) Let has type . If is not visible from , then there must be another reflex vertex such that its incident edges blocks the visibility of and restrains from seeing . So, the triangle contains . Thus, and lie on the either side of the line through and (see Figure 2), which is a contradiction since and are contained in the same cell . Hence, sees . Since are in the same cell, they lie on the same side of the supporting line of each incident edge of (see Figure 3). Thus, also has type . The reverse direction is symmetric to the forward direction.
Figure 2. The line through two reflex vertices separates and .
Figure 3. The positions of and relative to the incident edges of .
(2) Let be an available type for and is admissible for in . So, , and hence using Lemma 20. If , then there must be an edge of such that and lie on the either side of the supporting line of . As , and lie in different cells of , which is a contradiction. So, , and hence using Lemma 20. Now, we have . If , then we are done, since . Otherwise, let . Let for some point , a reflex vertex and . Using Lemma 27, . Observe that, is the polygonal path () between and which does not contain . Suppose, for contradiction, we assume that, . Then, lie on the either side of the line through and (see Figure 4).
Figure 4. A reflex vertex on the boundary arc .
So, and lie in different cells of , since . This is a contradiction. Therefore, , and hence using Lemma 27. Thus, is admissible for in . The reverse direction is symmetric to the forward direction.
Obtaining a suitable family: Let and be an available type for . By Lemma 31, set of all admissible entries are same for all points of . Thus, we define, . For each and , since , and is a simple polygonal path. So, each can be represented as an interval on -axis by a suitable parametrization. Also, by Lemma 18, admissible entries are disjoint exactly when their arcs are. Thus, can be represented as a set of intervals on -axis, where let be the interval corresponding to the entry . Assign weight to , where is the entry of the state . Thus we get a family by solving weighted interval scheduling problem with input and weight for . Running time for obtaining is . The following observation follows directly from Lemma 28 and the above argument.
Observation 32. For , works for if and only if .
Lemma 33. Let and be an available type for . Then, there exists a vertex () of the cell such that for each .
Proof. For any , let be the line through and . The cap of any point on associated with is equal to . Now consists of two connected convex regions and . Let be the region such that all the points of and the edges incident to lie on the same side of . Then for any point , we have . Observe that, there exist a vertex of the cell such that , since there are exactly two tangents from to and if we choose a vertex responsible for the suitable tangent (the tangent such that the cell and the edges incident to lie on the either side of that tangent) as , then is empty and consists of the whole . Call that vertex . So, we have for each .

Figure 1 (PDF p. 11).
Brief Description of Algorithm 1. The algorithm first handles the special case when the polygon is convex, i.e., has no reflex vertex (line 1) and initializes all states as empty (line 2). It then processes the states in increasing order of , constructing an arrangement from the entries of previously computed rows (lines 3–4) using computed in line 11. For each cell and each available type, it finds a maximum-weight collection of pairwise disjoint admissible entries using weighted interval scheduling (lines 5–7). If these entries can form a witness set of the required size, it updates the corresponding state with the smallest cap and stores the information needed to reconstruct the witness set explicitly (lines 8–10). It then computes the regions associated with the newly obtained entries (line 11). Finally, it constructs an arrangement for the root, evaluates each cell to find the largest possible witness set, and returns its size along with the corresponding records (lines 12–16).
Lemma 34. After completing row of Algorithm 1, the entry for is exactly , and its child record is admissible throughout its recorded cell.
Proof. By induction on . By Lemma 28 and Lemma 31, a cell contributes working caps to a state exactly when its schedule is heavy enough, and Lemma 33 computes the infimum over that cell. Caps of one type are nested, so the smallest cell value is the intersection over all contributing cells.
Lemma 35. Algorithm 1 returns .
Proof. For every root cell, the chosen entries (after interval scheduling) are disjoint and avoided by . So, using Observation 23, we get witnesses, and . Thus, . Conversely, hang the tree of a largest witness set from a witness . The caps two levels below work for defined states, have total weight , are disjoint, and miss . Their entries do as well. The sets are closed and miss , so can be moved into an open cell of that keeps every avoidance. By Lemma 31 the representative of that cell admits the same family.
Proof of Theorem 1. If , the polygon is convex, every point sees all of , and one witness is the best possible, which is what line 1 returns. Now let . By Lemma 5, no witness set has more than points, so the rows cover every possible size. The rows are filled in increasing order of . By Lemma 34, after row is finished, the entry of every state is exactly the smallest cap . Together with this entry, line 10 stores a cell, an extreme corner (Lemma 33), and a child record (Remark 29): a family of lower states whose entries are pairwise disjoint, are admissible throughout the stored cell (Lemma 31), and have total weight exactly . By Lemma 35, the value returned in line 16 equals . To output actual points, we start from a root cell with the largest value and place a witness at . The entries chosen for this cell are pairwise disjoint and are not seen by (Lemma 20). For each chosen state, we place one witness inside its stored cell, very close to its stored corner. The cap of this point is then very close to the entry , so it stays disjoint from its siblings, stays unseen by its parent, and stays inside its parent’s cap; the reconstruction section shows that such points exist. We then do the same for the child record of this state, and so on down to row 1. At every level, Observation 23 shows that the points chosen so far form a witness set. A state of weight contributes its own witness and, through its child record, more, so the final set has exactly points.
(Running Time) The dynamic programming table has rows. Before row is filled, the table holds at most entries, and each set has edges. So the arrangement has lines, it can be built in time, and it has cells. In each cell we do three things. First, we compute the visibility region of in time. This region tells us which types are available, and there are at most of them. Second, we check which earlier entries are avoided by . Each is prepared for point location when it is created in line 11, so one check takes time, and all checks in a cell take time. These checks do not depend on the type, so we do them only once per cell. Third, for each available type, we test containment with Lemma 27 in constant time per entry, and then solve one weighted interval scheduling problem with intervals. Sorting the intervals makes this cost . The third step is the most expensive one: it costs per cell, and therefore per row. Lines 8–11 cost less than this. Over all rows, the total is . The final phase in lines 12–16 visits cells and solves one scheduling problem in each. It costs , so it does not change the bound.
AI Disclosure. ChatGPT was used to assist with language editing, polishing, manuscript organization, figure preparation, and improving the clarity of exposition. Additionally, ChatGPT provided limited technical assistance in the development of the dynamic programming approach. All geometric characterizations were developed independently by the authors, with most of them established in our earlier work [11]. The authors take full responsibility for the correctness, originality, and scientific content of the manuscript.
Acknowledgment: The authors would like to thank Bodhayan Roy for several helpful discussions.
References
- [1]Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ∃r-complete. J. ACM, 69(1):4:1–4:70, 2022.
- [2]Yoav Amit, Joseph S. B. Mitchell, and Eli Packer. Locating guards for visibility coverage of polygons. Int. J. Comput. Geom. Appl., 20(5):601–630, 2010.
- [3][DDJ+25] Udvas Das, Binayak Dutta, Satyabrata Jana, Debabrata Pal, and Sasanka Roy. Witness set in monotone polygons: Exact and approximate. CoRR, abs/2511.10224, 2025. 3arxiv.org/abs/2511.10224
- [4][DDJ+26] Udvas Das, Binayak Dutta, Satyabrata Jana, Debabrata Pal, and Sasanka Roy. Witness set in monotone polygons: Exact and approximate. SIAM J. Discret. Math., 2026. To appear. 3arxiv.org/abs/2511.10224
- [5][DFM+19] Ovidiu Daescu, Stephan Friedrichs, Hemant Malik, Valentin Polishchuk, and Christiane Schmidt. Altitude terrain guarding and guarding uni-monotone polygons. Comput. Geom., 84:22–35, 2019. 2arxiv.org/abs/1803.05893
- [6][DMR26] Udvas Das, Shouvik Mondal, and Sasanka Roy. Witness set in weak visibility polygons is polynomial-time solvable. CoRR, abs/2609.24460, 2026. 3arxiv.org/abs/2609.24460
- [7][ESW01] Stephan J. Eidenbenz, Christoph Stamm, and Peter Widmayer. Inapproximability results for guarding polygons and terrains. Algorithmica, 31(1):79–113, 2001. 2DOI
- [8][Fis78] Steve Fisk. A short proof of chvátal’s watchman theorem. J. Comb. Theory B, 24(3):374, 1978. 5DOI
- [9][Fra89] Wm. Randolph Franklin. Art gallery theorems and algorithms (joseph o’rourke). SIAM Rev., 31(2):342–343, 1989. 1DOI
- [10][Gho07] Subir Kumar Ghosh. Visibility algorithms in the plane. Cambridge university press, 2007. 1DOI
- [11][JPRR26] Satyabrata Jana, Debabrata Pal, Bodhayan Roy, and Sasanka Roy. Witness set: A visibility problem in NP ∩ XP. CoRR, abs/2605.01592, 2026. 3, 5, 12arxiv.org/abs/2605.01592
- [12][LL86] D. T. Lee and Arthur K. Lin. Computational complexity of art gallery problems. IEEE Trans. Inf. Theory, 32(2):276–282, 1986. 2


