betaFeedback

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 ∃R\exists\mathbb{R}-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 nn vertices, of which ρρ are reflex, assuming that no three vertices are collinear. Our algorithm runs in O(ρ4n6log⁡n)\mathcal{O}(ρ^4n^6\log n) 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 p,qp, q in a polygon PP are said to be visible to each other if the line segment pq‾\overline{pq} lies entirely in PP. The visibility region of a point p∈Pp \in P, denoted by Vis⁡(p)\operatorname{Vis}(p), consists of all points of PP visible from pp.

A natural packing counterpart to the Art Gallery problem is the Witness Set problem, introduced by Amit, Mitchell, and Packer [2]. A point set W⊆PW \subseteq P is called a witness set if the visibility regions of its points are pairwise disjoint, that is, Vis⁡(u)∩Vis⁡(v)=∅\operatorname{Vis}(u) \cap\operatorname{Vis}(v) = \varnothing for every pair of distinct witnesses u,v∈Wu, v \in W (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 ∣W∣|W| 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 P\mathcal{P} with nn vertices. Output: A maximum-cardinality point set W⊆PW \subseteq\mathcal{P} such that Vis⁡(u)∩Vis⁡(v)=∅\operatorname{Vis}(u) \cap\operatorname{Vis}(v) = \varnothing for every pair of distinct points u,v∈Wu,v \in W.

We denote the maximum cardinality of a witness set in P\mathcal{P} by μWS(P)\mu_{\mathrm{WS}}(\mathcal{P}). 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 ∃R\exists\mathrm{R}-complete, even for polygons with integer coordinates. Consequently, it does not belong to NP unless NP=∃R\mathrm{NP} = \exists\mathrm{R}. 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

A simple polygon with a witness set

Figure 1. A simple polygon P\mathcal{P} with a witness set W={w1,…,w9}W = \{w_1,\ldots,w_9\}. 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 ρO(k)nO(1)\rho^{O(k)}n^{O(1)}, where ρ\rho is the number of reflex vertices and kk 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 O(nlog⁡n+ρ2(n+ρ2))O(n\log n+\rho^2(n+\rho^2)) 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 nf(k)n^{f(k)}, for a computable function ff, and reduces the continuous problem to a discrete instance. This yields an exact algorithm whose running time is polynomial for every fixed value of kk, but whose exponent depends on kk. 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 nn be the number of vertices of the polygon and ρ\rho the number of its reflex vertices.

Theorem 1. For a simple polygon P\mathcal{P} with nn vertices, ρ\rho of them reflex, and no three vertices on a line, a maximum witness set can be computed in O(ρ4n6log⁡n)O(\rho^4n^6\log n) 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 WW in a simple polygon P\mathcal{P}. 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 (α,r,i)(\alpha, r, i), where α\alpha denotes the number of witnesses, rr is a reflex vertex, and i∈{1,2}i \in\{1,2\} specifies one of the two sides associated with rr. The corresponding dynamic programming entry represents the smallest limiting cap of type (r,i)(r,i) that can support α\alpha witnesses.

By the classical art gallery theorem, every witness set contains at most ⌊n/3⌋\lfloor n/3\rfloor points. Consequently, the number of states is at most 2ρ⌊n/3⌋2\rho\lfloor n/3\rfloor, 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 PP, we denote its boundary by δ(P)\delta(P) and its interior by int⁡(P)\operatorname{int}(P). A vertex of PP is convex if its interior angle is at most 180∘180^\circ; otherwise, it is reflex. Let nn and ρ\rho be the number of vertices and the reflex vertices of PP respectively. For a line segment [a,b][a,b], we denote its interior by int⁡([a,b]):=[a,b]∖{a,b}\operatorname{int}([a,b]) := [a,b] \setminus\{a,b\} and its boundary by δ([a,b]):={a,b}\delta([a,b]) := \{a,b\}.

Definition 3. Two points x,y∈Px,y \in P are visible to each other if the segment xy‾\overline{xy} is contained entirely in PP. The visibility region of pp is Vis⁡(p)={q∈P:pq‾⊆P}\operatorname{Vis}(p) = \{q \in P : \overline{pq} \subseteq P\}. For a set S⊆PS \subseteq P, Vis⁡(S)=⋃p∈SVis⁡(p)\operatorname{Vis}(S) = \bigcup_{p \in S} \operatorname{Vis}(p).

Definition 4. In a polygon PP, a finite point set W⊆PW \subseteq P is said to be a witness set of PP if Vis⁡(x)∩Vis⁡(y)=∅\operatorname{Vis}(x) \cap\operatorname{Vis}(y) = \varnothing for all distinct x,y∈Wx,y \in W. A witness point is a point of WW. See Figure 1.

Lemma 5. Every witness set has at most ⌊n/3⌋\lfloor n/3 \rfloor points.

Proof. By Fisk’s proof of the art gallery theorem [8], some ⌊n/3⌋\lfloor n/3 \rfloor vertices see all of PP. Each of them sees at most one witness. □

Definition 6. Let p∈Pp \in P. Suppose pp sees a reflex vertex rr, and the ray from pp through rr goes on into the interior of PP after rr. Define hr(p)∈δ(P)h_r(p) \in\delta(P) to be the boundary point on this ray such that it goes outside PP after hr(p)h_r(p). The segment F=[r,hr(p)]F = [r,h_r(p)] is a window of pp.

For a point p∈Pp \in P, let F=[r,hr(p)]F = [r,h_r(p)] be a window of pp and e1,e2e_1,e_2 be the two incident edges of rr. For i∈{1,2}i \in\{1,2\}, let γi\gamma_i be the path from rr to hr(p)h_r(p) along δ(P)\delta(P) such that eie_i lies in γi\gamma_i. For i∈{1,2}i \in\{1,2\}, let RiR_i be the region bounded by the path γi\gamma_i and the line segment [r,hr(p)][r,h_r(p)]. Then, R1∪R2=PR_1 \cup R_2 = P (since γ1∪γ2=δ(P)\gamma_1 \cup\gamma_2 = \delta(P)) and exactly one of RiR_i contains pp.

Definition 7. We call RiR_i the contained side of FF if it contains pp, written PF(p)P_F(p), and the other region the pocket side of FF.

Definition 8. A point pp has type (r,i)(r,i), for i∈{1,2}i \in\{1,2\}, if RiR_i contains pp. We define the cap of pp associated with (r,i)(r,i) as PF(p)P_F(p) and denote it by Hr,i(p)H_{r,i}(p). We define its boundary arc A(Hr,i(p)):=Hr,i(p)∩δ(P)A(H_{r,i}(p)) := H_{r,i}(p) \cap\delta(P), which is precisely γi\gamma_i. We also define the corresponding window of Hr,i(p)H_{r,i}(p) to be F(Hr,i(p)):=FF(H_{r,i}(p)) := F.

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 pp lies on the line ll joining two reflex vertices (both of which are visible from pp and lies on the same side of pp) such that the pairs of edges of those reflex vertices lies on the either side of ll. Note that, in that case, Vis⁡(p)\operatorname{Vis}(p) 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 FF of a point ww, we have Vis⁡(w)⊆PF(w)\operatorname{Vis}(w) \subseteq P_F(w).

Definition 11. For two points p,q∈Pp,q \in\mathcal{P}, if q∉Vis⁡(p)q \notin\operatorname{Vis}(p), then qq lies in exactly one pocket side of pp for some window of pp. We call it a window of pp facing qq and denote it by Cp(q)C_p(q).

Lemma 12. Let p,q∈Pp,q \in\mathcal{P} with q∉Vis⁡(p)q \notin\operatorname{Vis}(p). Put C=Cp(q)C=C_p(q) and D=Cq(p)D=C_q(p). Then Vis⁡(p)∩Vis⁡(q)=∅\operatorname{Vis}(p) \cap\operatorname{Vis}(q)=\varnothing if and only if CC and DD are disjoint and DD lies on the pocket side of CC.

Proof. If the regions are disjoint, so are C⊆Vis⁡(p)C \subseteq\operatorname{Vis}(p) and D⊆Vis⁡(q)D \subseteq\operatorname{Vis}(q). The region Vis⁡(q)\operatorname{Vis}(q) is connected, contains qq and DD, and misses CC, so it stays on the pocket side of CC. Conversely, two disjoint chords cut P\mathcal{P} into two outer parts and a middle part. The hypotheses place pp and qq in different outer parts, and Observation 10 places their visibility regions there as well.

Witness Tree

Definition 13. For a witness set WW, define the graph T(W)T(W) with one node for each region Vis⁡(w)\operatorname{Vis}(w), w∈Ww \in W, and one node for each connected component of P∖⋃w∈WVis⁡(w)\mathcal{P} \setminus\bigcup_{w \in W} \operatorname{Vis}(w). Join two nodes if their regions meet along a window.

Remark 14.

  • For any two witnesses w1,w2∈Ww_1,w_2 \in W, their distance in T(W)T(W) is always even, since there is at least one connected component of P∖⋃w∈WVis⁡(w)\mathcal{P} \setminus\bigcup_{w \in W} \operatorname{Vis}(w) between Vis⁡(w1)\operatorname{Vis}(w_1) and Vis⁡(w2)\operatorname{Vis}(w_2).

  • For a node corresponding to Vis⁡(w)\operatorname{Vis}(w), we simply use ww as shorthand notation.

Lemma 15. For a witness set WW, T(W)T(W) is a tree.

Proof. For each w∈Ww \in W, the windows of ww lies in distinct rays from ww and no window contains ww. So all the windows of ww are disjoint. Windows of different witnesses lie in disjoint visibility regions, so they are disjoint. Let S={s1,…,sd}S=\{s_1,\ldots,s_d\} denote the collection of all windows of the points in WW. We cut P\mathcal{P} along these windows one at a time. For each i∈[d]i \in[d], we consider a graph GiG_i with one node for each connected component of P∖⋃j≤isj\mathcal{P} \setminus\bigcup_{j \leq i} s_j and there is an edge between two nodes if their corresponding components lie on either side of some sjs_j, j≤ij \leq i. Observe that, Gd=T(W)G_d=T(W). Since s1s_1 is a chord, it divides the polygon into two parts, G1G_1 has two nodes which are connected by a single edge. So, G1G_1 is a tree. Now, assume that Gi−1G_{i-1} is a tree. Let sis_i lies on the component cc of P∖⋃j≤i−1sj\mathcal{P} \setminus\bigcup_{j \leq i-1} s_j. sis_i cuts cc into two parts c1c_1 and c2c_2, so there is an edge between c1c_1 and c2c_2 in GiG_i and hence GiG_i is connected. Only one new edge has been introduced to GiG_i and two new nodes replaced one old node. Thus ∣E(Gi)∣=∣V(Gi)∣−1|E(G_i)|=|V(G_i)|-1 since ∣E(Gi)∣=∣E(Gi−1)∣+1|E(G_i)|=|E(G_{i-1})|+1, ∣V(Gi)∣=∣V(Gi−1)∣+1|V(G_i)|=|V(G_{i-1})|+1 and ∣E(Gi−1)∣=∣V(Gi−1)∣−1|E(G_{i-1})|=|V(G_{i-1})|-1. So GiG_i is a tree and hence T(W)=GdT(W)=G_d is a tree by induction.

Lemma 16. Let rr be a reflex vertex with incident edges e1e_1 and e2e_2. Let CC be the set of all caps associated with (r,i)(r,i) for i∈{1,2}i \in\{1,2\}, arising from the points of type (r,i)(r,i). Then the elements of CC are totally ordered by inclusion.

Proof. Two windows that start at rr cannot cross elsewhere. The cap with the shorter boundary arc is therefore contained in the other one.

Observation 17. Let KK be a cap and p,qp,q be two points in P\mathcal{P} such that p∈Kp \in K, q∉Kq \notin K. Then any path between pp and qq must intersect F(K)F(K).

Lemma 18. Let K1,K2K_1,K_2 be two caps. Then the followings are true.

  1. K1∩K2=∅K_1 \cap K_2=\varnothing if and only if A(K1)∩A(K2)=∅A(K_1) \cap A(K_2)=\varnothing.

  1. K1⊆K2K_1 \subseteq K_2 if and only if A(K1)⊆A(K2)A(K_1) \subseteq A(K_2).

Proof. For (1), one direction holds because the arcs lie in the caps. For the reverse direction, observe that KjK_j is precisely the closed region bounded by AKjA_{K_j} and FKjF_{K_j}. Since the endpoints of FKjF_{K_j} lies in AKjA_{K_j} and AK1∩AK2=∅A_{K_1} \cap A_{K_2} = \emptyset, FK1F_{K_1} and FK2F_{K_2} are also disjoint. Thus the regions bounded by AKjA_{K_j} and FKjF_{K_j} are disjoint. Hence K1∩K2=∅K_1 \cap K_2 = \emptyset.

Now, let K1⊆K2K_1 \subseteq K_2. Then, A(K1)=K1∩∂(P)⊆K2∩∂(P)=A(K2)A(K_1) = K_1 \cap\partial(P) \subseteq K_2 \cap\partial(P) = A(K_2). For the reverse direction, let A(K1)⊆A(K2)A(K_1) \subseteq A(K_2). Since KiK_i is the region bounded by the simple polygonal chain A(Ki)A(K_i) and the line segment F(Ki)F(K_i), K1⊆K2K_1 \subseteq K_2.

Definition 19. For a cap KK, define RK:=K∪Vis⁡(F(K))R_K := K \cup\operatorname{Vis}(F(K)).

Lemma 20. For a point p∈Pp \in\mathcal{P}, we have Vis⁡(p)∩K=∅\operatorname{Vis}(p) \cap K = \emptyset if and only if p∉RKp \notin R_K.

Proof. Let Vis⁡(p)∩K=∅\operatorname{Vis}(p) \cap K = \emptyset. As p∈Vis⁡(p)p \in\operatorname{Vis}(p), p∉Kp \notin K. If p∈Vis⁡(FK)p \in\operatorname{Vis}(F_K), then there exists q∈FK⊆Kq \in F_K \subseteq K such that qq sees pp which implies that q∈K∩Vis⁡(p)q \in K \cap\operatorname{Vis}(p), a contradiction. Thus p∉RKp \notin R_K. Conversely, let x∈Vis⁡(p)∩Kx \in\operatorname{Vis}(p) \cap K. Now p∉Kp \notin K since p∉RKp \notin R_K. So, using Observation 17, the visibility line segment [p,x][p,x] intersects FKF_K at yy (let). Thus p∈Vis⁡(FK)p \in\operatorname{Vis}(F_K), a contradiction.

Definition 21. A witness set WW is confined to a set SS if Vis⁡(w)⊆S\operatorname{Vis}(w) \subseteq S for all w∈Ww \in W.

Lemma 22. Root T(W)T(W) at a witness point w∈Ww \in W. For any other witness u∈Wu \in W, let Fu=Cu(w)F_u = C_u(w) (a window of uu facing ww) and let Hu=PFu(u)H_u = P_{F_u}(u). Let WuW_u be the set of witness points which are in the subtree rooted at uu. Then WuW_u is confined to the cap HuH_u. Let v1,v2∈Wv_1, v_2 \in W are distance two descendants of uu in T(W)T(W). Then Hv1∩Hv2=∅H_{v_1} \cap H_{v_2} = \emptyset, Hvi⊊HuH_{v_i} \subsetneq H_u, and Hvi∩Vis⁡(u)=∅H_{v_i} \cap\operatorname{Vis}(u) = \emptyset for each i∈{1,2}i \in\{1,2\}.

Moreover, if WW is confined to a cap HH of the root ww, then Hu⊆HH_u \subseteq H.

Proof. The chord FuF_u divides P\mathcal{P} into two pieces one of which is HuH_u and the other one is the pocket side of FuF_u. Let v∈Wuv \in W_u. Clearly, Vis⁡(v)\operatorname{Vis}(v) is contained in exactly one of the pieces since Vis⁡(v)∩Vis⁡(u)=∅\operatorname{Vis}(v) \cap\operatorname{Vis}(u) = \emptyset, Fu⊆Vis⁡(u)F_u \subseteq\operatorname{Vis}(u) and Vis⁡(v)\operatorname{Vis}(v) is a connected region. Now, if Vis⁡(v)\operatorname{Vis}(v) is contained in the pocket side of FuF_u, then Vis⁡(w)\operatorname{Vis}(w) and Vis⁡(v)\operatorname{Vis}(v) are in the same side of FuF_u. which implies there is a path in T(w)T(w) from the root to vv which does not contain uu. This contradicts the tree structure of T(w)T(w) since vv lies in the subtree rooted at uu so the path from ww to vv must go through uu. Thus, Vis⁡(v)⊂Hu\operatorname{Vis}(v) \subset H_u and WuW_u is confined to HuH_u. Observe that, HviH_{v_i} is the union of the regions descendant to viv_i and Vis⁡(vi)\operatorname{Vis}(v_i). Thus Hv1∩Hv2=∅H_{v_1} \cap H_{v_2} = \emptyset, since descendants of v1v_1 and v2v_2 are disjoint and Vis⁡(v1)∩Vis⁡(v2)=∅\operatorname{Vis}(v_1) \cap\operatorname{Vis}(v_2) = \emptyset. Now, Vis⁡(u)\operatorname{Vis}(u) lies on the pocket side of FviF_{v_i} since Cvi(u)=Cvi(w)C_{v_i}(u) = C_{v_i}(w). So, Hvi⊊HuH_{v_i} \subsetneq H_u and Hvi∩Vis⁡(u)=∅H_{v_i} \cap\operatorname{Vis}(u) = \emptyset. If WW is confined to a cap HH of ww, then HH is the union of the regions descendant to ww and Vis⁡(w)\operatorname{Vis}(w). Hence, Hu⊆HH_u \subseteq H because HuH_u is also the union of the regions descendant to uu and Vis⁡(u)\operatorname{Vis}(u).

Observation 23. Let ww be a point and HH be a cap of ww. For i∈{1,…,m}i \in\{1,\ldots,m\}, let KiK_i be a cap such that the KiK_i are pairwise disjoint, Ki∩Vis⁡(w)=∅K_i \cap\operatorname{Vis}(w) = \emptyset and there is a witness set WiW_i of size tit_i confined to KiK_i. Then W′={w}∪(⋃i=1mWi)W' = \{w\} \cup\left(\bigcup_{i=1}^m W_i\right) is a witness set of size 1+∑i=1mti1 + \sum_{i=1}^m t_i. Moreover, if each KiK_i is contained in a cap HH of ww, then W′W' is confined to HH.

The Dynamic Programming

Definition 24. A state is a triple s=(α,r,i)s = (\alpha,r,i) with 1≤α≤⌊n/3⌋1 \leq\alpha\leq\lfloor n/3 \rfloor, a reflex vertex rr and i∈{1,2}i \in\{1,2\}. A cap Hr,i(w)H_{r,i}(w) of ww works for ss if some witness set U⊆RU \subseteq R of size α\alpha contains ww and is confined to the cap. For a state s=(α,r,i)s = (\alpha,r,i), we define nw⁡(s)=α\operatorname{nw}(s) = \alpha. Let H(s)\mathcal{H}(s) be the family of caps that work for ss and define K∗(s):=⋂H∈H(s)HK^*(s) := \bigcap_{H \in\mathcal{H}(s)} H.

Let h=⌊n/3⌋h = \lfloor n/3 \rfloor. There are at most 2ρh2\rho h states since 1≤α≤h1 \le\alpha\le h, ρ\rho is the number of reflex vertices and i∈{1,2}i \in\{1,2\}. Deleting a witness keeps a set confined. Hence, we have the following observation.

Observation 25. Let β≤α\beta\le\alpha. If a cap HH works for (α,r,i)(\alpha,r,i), then HH also works for (β,r,i)(\beta,r,i). Moreover, K∗(α,r,i)≠∅⇒K∗(β,r,i)≠∅K^*(\alpha,r,i) \ne\varnothing\Rightarrow K^*(\beta,r,i) \ne\varnothing and K∗(β,r,i)⊆K∗(α,r,i)K^*(\beta,r,i) \subseteq K^*(\alpha,r,i).

Definition 26. Let ww be regular with a cap HH. A cap KK is called admissible for ww in HH if Vis⁡(w)∩K=∅\operatorname{Vis}(w) \cap K = \varnothing and K⊆HK \subseteq H. KK is called root-admissible for ww if Vis⁡(w)∩K=∅\operatorname{Vis}(w) \cap K = \varnothing.

Lemma 27. Let HH be a cap of ww, and let KK be a cap at some reflex vertex rr such that Vis⁡(w)∩K=∅\operatorname{Vis}(w) \cap K = \varnothing. Then K⊆HK \subseteq H if and only if r∈A(H)r \in A(H).

Proof. We have Vis⁡(w)∩K=∅\operatorname{Vis}(w) \cap K = \varnothing. For the forward direction, let K⊆HK \subseteq H. Then, r∈A(H)r \in A(H), since A(K)⊆A(H)A(K) \subseteq A(H) (using Lemma 18) and r∈A(K)r \in A(K). Now, for the reverse direction, let r∈A(H)r \in A(H). If KK is not contained in HH, there exists y∈K∖Hy \in K \setminus H. Since KK is connected, there is a path γ⊆K\gamma\subseteq K between yy and rr. Now, r∈Hr \in H and y∉Hy \notin H, so γ\gamma must intersect F(H)⊆Vis⁡(w)F(H) \subseteq\operatorname{Vis}(w) using Observation 17. Thus, Vis⁡(w)∩K≠∅\operatorname{Vis}(w) \cap K \ne\varnothing, which is a contradiction.

Lemma 28. The cap Hr,i(w)H_{r,i}(w) works for s=(α,r,i)s = (\alpha,r,i) if and only if there exist states s1,…,sms_1,\ldots,s_m satisfying the following properties for some m≥0m \ge0.

  1. nw⁡(sj)<nw⁡(s)\operatorname{nw}(s_j) < \operatorname{nw}(s), for each j∈[m]j \in[m].

  2. K∗(sj)K^*(s_j) are pairwise disjoint and each is non-empty and admissible for ww in Hr,i(w)H_{r,i}(w).

  3. 1+∑j=1mnw⁡(sj)≥α1 + \sum_{j=1}^{m} \operatorname{nw}(s_j) \ge\alpha.

Clearly, for α=1\alpha= 1, the empty family is allowed since any cap of ww associated to (r,i)(r,i) works for (1,r,i)(1,r,i).

Proof. For the forward direction, let H=Hr,i(w)H = H_{r,i}(w) works for s=(α,r,i)s = (\alpha,r,i). Let WwW_w be a witness set confined to HH such that w∈Www \in W_w and ∣Ww∣=α\lvert W_w \rvert= \alpha. Now, we consider the tree T(Ww)\mathcal{T}(W_w) rooted at ww. Let v1,…,vmv_1,\ldots,v_m are the distance two descendants of ww. Let Fj=(Cvj(w))F_j = (C_{v_j}(w)) and Hj=PFj(vj)H_j = P_{F_j}(v_j). Let αj\alpha_j be the size of subtree of T(Ww)\mathcal{T}(W_w) rooted at vjv_j, and let rjr_j be a reflex vertex and ij∈{1,2}i_j \in\{1,2\} be such that Hj=Hrj,ij(vj)H_j = H_{r_j,i_j}(v_j). So, α=1+∑j=1mαj\alpha= 1 + \sum_{j=1}^{m} \alpha_j. Define sj=(αj,rj,ij)s_j = (\alpha_j,r_j,i_j) for each j∈[m]j \in[m]. The conditions (1) and (3) are satisfied, since nw⁡(sj)=αj\operatorname{nw}(s_j) = \alpha_j. Now, using Lemma 22, HjH_j are pairwise disjoint, Hj⊊HH_j \subsetneq H, and Hj∩Vis⁡(w)=∅H_j \cap\operatorname{Vis}(w) = \varnothing. Thus, condition (2) is also satisfied because K∗(sj)⊆HjK^*(s_j) \subseteq H_j for each jj.

For the reverse direction, let s=(α,r,i)s = (\alpha,r,i) be a state and there are states s1,…,sms_1,\ldots,s_m satisfying the three conditions. Let WjW_j be a witness set of size nw⁡(sj)\operatorname{nw}(s_j) confined in K∗(sj)K^*(s_j), and W′={w}∪(⋃j=1mWj)W' = \{w\} \cup\left(\bigcup_{j=1}^{m} W_j\right), α′=1+∑j=1mnw⁡(sj)\alpha' = 1 + \sum_{j=1}^{m} \operatorname{nw}(s_j). Thus, using Observation 23, W′W' is a witness set of size α′\alpha' confined in Hr,i(w)H_{r,i}(w). So, Hr,i(w)H_{r,i}(w) works for (α′,r,i)(\alpha',r,i) as well as (α,r,i)(\alpha,r,i) using Observation 25.

Remark 29. Suppose Hr,i(w)H_{r,i}(w) works for s=(α,r,i)s = (\alpha,r,i) then there exist states s1,…,sms_1,\ldots,s_m satisfying the three properties of Lemma 28. Now, by Observation 25, we can always choose a family s1′,…,sm′s'_1,\ldots,s'_m such that it satisfies the first two properties of Lemma 28 with the equality 1+∑j=1mnw⁡(sj′)=α1 + \sum_{j=1}^{m} \operatorname{nw}(s'_j) = \alpha. We call such a family a child record of ss.

Algorithm for Finding Maximum Witness Set

Define K<α:={K∣K=K∗(s)\mathcal{K}_{<\alpha}:=\{K\mid K=K^*(s) for some state ss with nw⁡(s)<α}\operatorname{nw}(s)<\alpha\}. Let L1L_1 consists of the supporting lines of the edges of P\mathcal{P} and L2L_2 be the set of lines through a reflex vertex and another vertex. Now, define L3(α)L_3^{(\alpha)} to be the set of supporting lines of the edges of RKR_K for each K∈K<αK\in\mathcal{K}_{<\alpha}.

Definition 30. The arrangement of row α\alpha, denoted by Aα\mathcal{A}_\alpha, is defined as L1∪L2∪L3(α)L_1\cup L_2\cup L_3^{(\alpha)}. The lines of Aα\mathcal{A}_\alpha divide P\mathcal{P} into convex regions, which we call cells. Let CαC_\alpha denote the set of all such cells contained in P\mathcal{P}. The intersection of two distinct cells, if nonempty, lies entirely on their boundaries. For a cell cc, let g(c)g(c) be the arithmetic mean of all vertices of cc.

We have ∣L1∣=O(n)|L_1|=O(n), ∣L2∣=O(ρn)|L_2|=O(\rho n), ∣L3(α)∣=O(ρn2)|L_3^{(\alpha)}|=O(\rho n^2) since there are at most 2ρh=O(ρn)2\rho h=O(\rho n) states and RKR_K has O(n)O(n) edges for K∈K<αK\in\mathcal{K}_{<\alpha}. So, there are O(ρn2)O(\rho n^2) lines in Aα\mathcal{A}_\alpha. Now, the number of cells created by the lines in Aα\mathcal{A}_\alpha is O(∣Aα∣2)O(|\mathcal{A}_\alpha|^2). Thus, ∣Cα∣=O(ρ2n4)|C_\alpha|=O(\rho^2n^4).

Lemma 31. Let c∈Cαc\in C_\alpha and v1,v2v_1,v_2 be two points in iN(c)iN(c). Then the followings are true.

  1. v1v_1 has type (r,i)(r,i) if and only if v2v_2 has type (r,i)(r,i), i.e., the available types inside a cell remains same.

  1. For an available type (r,i)(r,i) and for K∈K<αK\in\mathcal{K}_{<\alpha}, KK is admissible for v1v_1 in Hr,i(v1)H_{r,i}(v_1) if and only if KK is admissible for v2v_2 in Hr,i(v2)H_{r,i}(v_2).

Proof. (1) Let v1v_1 has type (r,i)(r,i). If rr is not visible from v2v_2, then there must be another reflex vertex r′r' such that its incident edges blocks the visibility of v2v_2 and restrains v2v_2 from seeing rr. So, the triangle △v1v2r\triangle v_1v_2r contains r′r'. Thus, v1v_1 and v2v_2 lie on the either side of the line ll through rr and r′r' (see Figure 2), which is a contradiction since l∈L2l\in L_2 and v1,v2v_1,v_2 are contained in the same cell cc. Hence, v2v_2 sees rr. Since v1,v2v_1,v_2 are in the same cell, they lie on the same side of the supporting line of each incident edge of rr (see Figure 3). Thus, v2v_2 also has type (r,i)(r,i). The reverse direction is symmetric to the forward direction.

Figure 2. The line through two reflex vertices separates v1v_1 and v2v_2.

Figure 3. The positions of v1v_1 and v2v_2 relative to the incident edges of rr.

(2) Let (r,i)(r,i) be an available type for cc and K∈K<αK\in\mathcal{K}_{<\alpha} is admissible for v1v_1 in H1=Hr,i(v1)H_1=H_{r,i}(v_1). So, Vis⁡(v1)∩K=∅\operatorname{Vis}(v_1)\cap K=\varnothing, and hence v1∉RKv_1\notin R_K using Lemma 20. If v2∈RKv_2\in R_K, then there must be an edge ee of RKR_K such that v1v_1 and v2v_2 lie on the either side of the supporting line of ee. As e∈L3(α)e \in L_3^{(\alpha)}, v1v_1 and v2v_2 lie in different cells of CαC_\alpha, which is a contradiction. So, v2∉RKv_2 \notin R_K, and hence Vis⁡(v2)∩K=∅\operatorname{Vis}(v_2) \cap K = \varnothing using Lemma 20. Now, we have K⊂H1K \subset H_1. If H1⊆H2=Hr,i(v2)H_1 \subseteq H_2 = H_{r,i}(v_2), then we are done, since K⊂H1⊆H2K \subset H_1 \subseteq H_2. Otherwise, let H2⊊H1H_2 \subsetneq H_1. Let K=Hr′,i′(v)K = H_{r',i'}(v) for some point vv, a reflex vertex r′r' and i′∈{1,2}i' \in\{1,2\}. Using Lemma 27, r′∈A(H1)r' \in A(H_1). Observe that, A(H1)∖A(H2)A(H_1) \setminus A(H_2) is the polygonal path (⊂δ(P)\subset\delta(P)) between hr(v1)h_r(v_1) and hr(v2)h_r(v_2) which does not contain rr. Suppose, for contradiction, we assume that, r′∉A(H2)r' \notin A(H_2). Then, v1,v2v_1,v_2 lie on the either side of the line l′l' through rr and r′r' (see Figure 4).

Figure 4. A reflex vertex r′r' on the boundary arc A(H1)∖A(H2)A(H_1) \setminus A(H_2).

So, v1v_1 and v2v_2 lie in different cells of CαC_\alpha, since l′∈L2l' \in L_2. This is a contradiction. Therefore, r′∈A(H2)r' \in A(H_2), and hence K⊆H2K \subseteq H_2 using Lemma 27. Thus, K∈K<αK \in\mathcal{K}_{<\alpha} is admissible for v2v_2 in Hr,i(v2)H_{r,i}(v_2). The reverse direction is symmetric to the forward direction.

Obtaining a suitable family: Let c∈Cαc \in C_\alpha and (r,i)(r,i) be an available type for cc. By Lemma 31, set of all admissible entries are same for all points of iN(c)iN(c). Thus, we define, Qα,c:={K∈K<α∣K is admissible for x in Hr,i(x) for some x∈iN(c)}Q_{\alpha,c} := \{K \in\mathcal{K}_{<\alpha} \mid K \text{ is admissible for } x \text{ in } H_{r,i}(x) \text{ for some } x \in iN(c)\}. For each K∈Qα,cK \in Q_{\alpha,c} and x∈iN(c)x \in iN(c), A(K)⊊A(Hr,i(x))A(K) \subsetneq A(H_{r,i}(x)) since K⊊Hr,i(x)K \subsetneq H_{r,i}(x), and A(K)A(K) is a simple polygonal path. So, each A(K)A(K) can be represented as an interval on xx-axis by a suitable parametrization. Also, by Lemma 18, admissible entries are disjoint exactly when their arcs are. Thus, Qα,cQ_{\alpha,c} can be represented as a set Iα,cI_{\alpha,c} of intervals on xx-axis, where let lKl_K be the interval corresponding to the entry K∈Qα,cK \in Q_{\alpha,c}. Assign weight λK=nw⁡(s)\lambda_K = \operatorname{nw}(s) to lKl_K, where KK is the entry of the state ss. Thus we get a family Sα,c⊆Qα,cS_{\alpha,c} \subseteq Q_{\alpha,c} by solving weighted interval scheduling problem with input Iα,cI_{\alpha,c} and weight λK\lambda_K for lK∈Iα,cl_K \in I_{\alpha,c}. Running time for obtaining Sα,cS_{\alpha,c} is O(∣Qα,c∣log⁡(∣Qα,c∣))=O(ρnlog⁡(ρn))=O(ρnlog⁡n)O(|Q_{\alpha,c}| \log(|Q_{\alpha,c}|)) = O(\rho n \log(\rho n)) = O(\rho n \log n). The following observation follows directly from Lemma 28 and the above argument.

Observation 32. For x∈cx \in c, Hr,i(x)H_{r,i}(x) works for s=(α,r,i)s = (\alpha,r,i) if and only if 1+∑K∈Sα,cλK≥α1 + \sum_{K \in S_{\alpha,c}} \lambda_K \ge\alpha.

Lemma 33. Let c∈Cαc \in C_\alpha and (r,i)(r,i) be an available type for cc. Then, there exists a vertex vr,icv_{r,i}^c (≠r\ne r) of the cell cc such that Hr,i(vr,ic)⊆Hr,i(x)H_{r,i}(v_{r,i}^c) \subseteq H_{r,i}(x) for each x∈cx \in c.

Proof. For any y∈cy \in c, let lyl_y be the line through rr and yy. The cap of any point on ly∩cl_y \cap c associated with (r,i)(r,i) is equal to Hr,i(y)H_{r,i}(y). Now c∖lyc \setminus l_y consists of two connected convex regions R1yR_1^y and R2yR_2^y. Let R1yR_1^y be the region such that all the points of R1yR_1^y and the edges incident to rr lie on the same side of lyl_y. Then for any point y1∈Riyy_1 \in R_i^y, we have Hr,i(y1)⊆Hr,i(y)⊆Hr,i(y2)H_{r,i}(y_1) \subseteq H_{r,i}(y) \subseteq H_{r,i}(y_2). Observe that, there exist a vertex vv of the cell cc such that R1y=∅R_1^y = \varnothing, since there are exactly two tangents from rr to cc and if we choose a vertex responsible for the suitable tangent (the tangent such that the cell and the edges incident to rr lie on the either side of that tangent) as yy, then R1yR_1^y is empty and R2yR_2^y consists of the whole c∖lyc \setminus l_y. Call that vertex vr,icv_{r,i}^c. So, we have Hr,i(vr,ic)⊆Hr,i(x)H_{r,i}(v_{r,i}^c) \subseteq H_{r,i}(x) for each x∈cx \in c.

Algorithm 1: Cap table and root records

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 α\alpha, constructing an arrangement from the entries of previously computed rows (lines 3–4) using RKR_K computed in line 11. For each cell and each available type, it finds a maximum-weight collection Sα,cS_{\alpha,c} 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 α\alpha of Algorithm 1, the entry for s=(α,r,i)s=(\alpha,r,i) is exactly K∗(s)K^*(s), and its child record is admissible throughout its recorded cell.

Proof. By induction on α\alpha. 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 μWS(P)\mu_{\mathrm{WS}}(\mathcal{P}).

Proof. For every root cell, the chosen entries (after interval scheduling) are disjoint and avoided by g(c)g(c). So, using Observation 23, we get b(c)b(c) witnesses, and b(c)≤μWS(P)b(c) \le\mu_{\mathrm{WS}}(\mathcal{P}). Thus, max⁡cb(c)≤μWS(P)\max_c b(c) \le\mu_{\mathrm{WS}}(\mathcal{P}). Conversely, hang the tree of a largest witness set from a witness ww. The caps two levels below ww work for defined states, have total weight μWS(P)−1\mu_{\mathrm{WS}}(\mathcal{P})-1, are disjoint, and miss Vis⁡(w)\operatorname{Vis}(w). Their entries do as well. The sets RKR_K are closed and miss ww, so ww can be moved into an open cell of Aroot\mathcal{A}_{\mathrm{root}} that keeps every avoidance. By Lemma 31 the representative of that cell admits the same family.

Proof of Theorem 1. If ρ=0\rho= 0, the polygon is convex, every point sees all of P\mathcal{P}, and one witness is the best possible, which is what line 1 returns. Now let ρ≥1\rho\ge1. By Lemma 5, no witness set has more than h=⌊n/3⌋h = \lfloor n/3 \rfloor points, so the rows α=1,…,h\alpha= 1,\ldots,h cover every possible size. The rows are filled in increasing order of α\alpha. By Lemma 34, after row α\alpha is finished, the entry of every state s=(α,r,i)s = (\alpha,r,i) is exactly the smallest cap K∗(s)K^*(s). 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 α−1\alpha- 1. By Lemma 35, the value max⁡cb(c)\max_c b(c) returned in line 16 equals μWS(P)\mu_{\mathrm{WS}}(\mathcal{P}). To output actual points, we start from a root cell cc with the largest value b(c)b(c) and place a witness at g(c)g(c). The entries chosen for this cell are pairwise disjoint and are not seen by g(c)g(c) (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 K∗(s)K^*(s), 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 α\alpha contributes its own witness and, through its child record, α−1\alpha- 1 more, so the final set has exactly b(c)=μWS(P)b(c) = \mu_{\mathrm{WS}}(\mathcal{P}) points.

(Running Time) The dynamic programming table has O(h)=O(⌊n/3⌋)O(h) = O(\lfloor n/3 \rfloor) rows. Before row α\alpha is filled, the table holds at most 2ρh=O(ρn)2\rho h = O(\rho n) entries, and each set RKR_K has O(n)O(n) edges. So the arrangement Aα\mathcal{A}_\alpha has O(ρn2)O(\rho n^2) lines, it can be built in O(ρ2n4)O(\rho^2 n^4) time, and it has O(ρ2n4)O(\rho^2 n^4) cells. In each cell we do three things. First, we compute the visibility region of g(c)g(c) in O(n)O(n) time. This region tells us which types are available, and there are at most ρ\rho of them. Second, we check which earlier entries KK are avoided by g(c)g(c). Each RKR_K is prepared for point location when it is created in line 11, so one check takes O(log⁡n)O(\log n) time, and all checks in a cell take O(ρnlog⁡n)O(\rho n \log n) 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 O(ρn)O(\rho n) intervals. Sorting the intervals makes this cost O(ρnlog⁡n)O(\rho n \log n). The third step is the most expensive one: it costs O(ρ2nlog⁡n)O(\rho^2 n \log n) per cell, and therefore O(ρ4n5log⁡n)O(\rho^4 n^5 \log n) per row. Lines 8–11 cost less than this. Over all h=O(n)h = O(n) rows, the total is O(ρ4n6log⁡n)O(\rho^4 n^6 \log n). The final phase in lines 12–16 visits O(ρ2n4)O(\rho^2 n^4) cells and solves one scheduling problem in each. It costs O(ρ3n5log⁡n)O(\rho^3 n^5 \log n), so it does not change the bound. □\square

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. [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. [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. [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. [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. [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. [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. [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. [8][Fis78] Steve Fisk. A short proof of chvátal’s watchman theorem. J. Comb. Theory B, 24(3):374, 1978. 5DOI
  9. [9][Fra89] Wm. Randolph Franklin. Art gallery theorems and algorithms (joseph o’rourke). SIAM Rev., 31(2):342–343, 1989. 1DOI
  10. [10][Gho07] Subir Kumar Ghosh. Visibility algorithms in the plane. Cambridge university press, 2007. 1DOI
  11. [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. [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

Paper details

vlnc:W_hmuzhxmz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents