Finding a Shortest Curve That Separates Few Objects from Many
Abstract
We present a fixed-parameter tractable (FPT) algorithm to find a shortest curve that encloses a set of required objects in the plane while paying a penalty for enclosing unwanted objects.
The input is a set of interior-disjoint simple polygons in the plane, where of the polygons are required to be enclosed and the remaining optional polygons have non-negative penalties. The goal is to find a closed curve that is disjoint from the polygon interiors and encloses the required polygons, while minimizing the length of the curve plus the penalties of the enclosed optional polygons. If the penalties are high, the output is a shortest curve that separates the required polygons from the others. The problem is NP-hard if is not fixed, even in very special cases. The runtime of our algorithm is , where is the number of vertices of the input polygons.
We extend the result to a graph version of the problem where the input is a connected plane graph with positive edge weights. There are required faces; the remaining faces are optional and have non-negative penalties. The goal is to find a closed walk in the graph that encloses the required faces, while minimizing the weight of the walk plus the penalties of the enclosed optional faces. We also consider an inverted version of the problem where the required objects must lie outside the curve. Our algorithms solve some other well-studied problems, such as geometric knapsack.
Keywords and phrases:
Enclosure, curve, separation, weakly simple polygon, Euler tourFunding:
Therese Biedl: Natural Science and Engineering Research Council of Canada.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Computational geometry ; Theory of computation Parameterized complexity and exact algorithmsAcknowledgements:
This work was initiated at the Dagstuhl seminar 24072 “Triangulations in Geometry and Topology” in February 2024. We thank the organizers, Maike Buchin, Jean Cardinal, Arnaud de Mesmay, and Jonathan Spreer, as well as all participants, for the stimulating atmosphere. We also thank Alexander Wolff for significant contributions, Saul Schleimer for useful discussions, and the anonymous reviewers for their constructive feedback.Editors:
Oswin Aichholzer and Haitao WangSeries and Publisher:

1 Introduction
We investigate the separation problem of finding a shortest curve that encloses a subset of objects while excluding other objects. A very basic setting is for points in the plane: given points in the plane and a subset of size , find a minimum-perimeter polygon containing the specified points and excluding the other points. This problem is NP-hard when may be large, as proved by Eades and Rappaport [11] for the case via a simple reduction from the Travelling Salesman Problem.
As a special case of our main result, we give the first algorithm for this problem that is fixed-parameter tractable (FPT) in . Our result is far more general and applies in two settings, a geometric setting and a graph-theoretic setting.
Geometric-Enclosure-with-Penalties.
We generalize from point objects to objects that are interior-disjoint simple polygons in the plane, and we consider a weighted form of exclusion.
Input. The input is a set of simple interior-disjoint polygons partitioned into a set of required polygons and the remaining set of optional polygons. Each optional polygon comes with a non-negative penalty where we allow .
Output. The goal is to find a weakly simple polygon that does not intersect the interior of any input polygon and encloses all polygons of while minimizing the cost , which is defined to be the Euclidean length of plus the penalties of the polygons of that are inside .
See Figure 1 for an example. A polygon with penalty must be excluded. A polygon with penalty 0 may be included or excluded without making a difference, so it only acts as an obstacle to the solution curve. As Figure 1 illustrates, the problem would be ill-defined if we required the solution curve to be a simple polygon. The natural condition is that should be a weakly simple polygon, whose boundary may touch or overlap itself but not cross itself. We give a precise definition in Section 2.1. An important property is that a weakly simple polygon encloses a well-defined region. Our first main result is:
Theorem 1.
Geometric-Enclosure-with-Penalties for required polygons can be solved in time and space, if the input polygons have vertices in total.
If all objects are points, this can be handled by approximating each point by a small triangle. An exact solution for an arbitrary mix of point and polygon objects appears in [5, Appendix I].
Graph-Enclosure-with-Penalties.
In this setting, the objects are faces of a plane graph.
Input. The input is a simple connected plane graph and positive edge weights. The bounded faces of are partitioned into a set of required faces and the remaining set of optional faces. Each optional face has a penalty from .
Output. The goal is to find a weakly simple closed walk in such that faces of are inside while minimizing the cost which is defined to be the sum of the weights of the edges of plus the penalties of the faces of that are inside . See Figure 2 for an example. Intuitively, a weakly simple closed walk is one without crossings; we give a more precise definition in the full version of this paper [5, Appendix A]. For a weakly simple closed walk, the notions of inside and outside are well-defined. Our second main result is:
Theorem 2.
Graph-Enclosure-with-Penalties can be solved in time and space, where is the number of required faces and is the number of vertices of .
A common framework.
Although the two settings described above seem different, we resolve them into a common geometric framework, which we call Enclosure-with-Penalties. Our algorithm applies to this general problem. The basic idea is to transform the graph problem into a geometric problem by taking a straight-line embedding of the graph. The bounded faces of the graph become polygons slightly more general than simple polygons. We also consider the outer face as an unbounded polygon. Then the “free space” between the polygons consists only of the graph edges. This gives us a geometric problem, albeit with arbitrary positive edge weights defined on edges that have a polygon on each side. In Section 3 we define the Enclosure-with-Penalties problem by generalizing the Geometric-Enclosure-with-Penalties problem to include these instances.
We remark that the resulting algorithm for Theorem 2 makes essential use of the straight-line embedding of the input graph. In particular, the subproblems that we solve depend on the embedding. This imposition of geometry seems artificial, but oddly enough, we do not know how to formulate our algorithm in a purely combinatorial setting.
Our approach.
We use dynamic programming (Section 4) to build a polygon that is locally correct – we use segments that do not intersect the interior of any object and we account for required objects and tally the penalties as we add triangles to . We will prove that the cost computed by the algorithm is correct, but this is tricky because itself will not necessarily be weakly simple. “Inside” is no longer well-defined. Instead, we use winding numbers to give a measure of the cost of that matches the cost computed by the algorithm.
In Section 5 we give an algorithm to uncross to a weakly simple polygon without increasing its cost, which provides our final output. Correctness is proved in Section 6.
The run-time for the Uncrossing Algorithm is dominated by the run-time for the dynamic program. To obtain our claimed run-time we speed up the dynamic program in Section 7.
Lower bounds.
To complement our algorithms we prove that, under the Exponential Time Hypothesis (ETH), the Geometric- and Graph-Enclosure-with-Penalties problems cannot be solved in time, implying that the linear dependence on in the exponent of the running time of our algorithms is the best possible assuming ETH. The proof is a reduction from unweighted Planar Steiner Tree, which admits a lower bound by a result by Marx, Pilipczuk, and Pilipczuk [15, Theorem 1.2]. See [5, Appendix K].
Swapping the inside with the outside.
We extend our algorithm to an inverted version of the Enclosure-with-Penalties problem where the required objects have to be outside , and the objective is to minimize the length of plus the penalties of the polygons of that are outside . The runtime remains the same, see Section 8. This algorithm provides a new faster solution to the geometric knapsack problem discussed below.
Negative penalties.
We can allow some number of objects with negative penalties (rewards); in this case, the runtime is increased by a factor of . See [5, Appendix J].
1.1 Related work
Cut problems and separator problems in graphs have a long history, and separation problems in geometric settings are a natural and well studied counterpart.
Geometric knapsack problem.
Geometric separation problems were first explored by Eades and Rappaport [11] (as discussed above) and by Arkin, Khuller, and Mitchell, who introduced the geometric knapsack problem [4], which corresponds to the inverted version of the Geometric-Enclosure-with-Penalties problem in the special case where there are no required objects. (In their equivalent formulation, each object has a finite nonnegative value, and the goal is to compute a curve that maximizes the total value of the enclosed objects minus its length.) They gave an algorithm with running time [4, Theorem 6]. In the full version [5, Appendix M], we note some issues regarding weak simplicity and interior/exterior of their output. Since there are no required objects, our algorithm for the inverted problem solves the geometric knapsack problem in time .
Relation to homotopy and homology.
Our problem has a topological flavor and is therefore, in principle, amenable to homotopy and homology techniques. However, these techniques are unlikely to lead to algorithms that are FPT in , even assuming only infinite penalties. In particular, for the Graph-Enclosure-with-Penalties problem, enumerating a set of candidate homotopy classes, i.e., the possible ways how a solution winds around the objects to enclose the required objects and avoid the most undesirable ones, is possible using a technique by Chambers, Colin de Verdière, Erickson, Lazarus, and Whittlesey [7] (specifically, because the exchange argument [7, Proposition 4.2] is also valid for our problem), but this results in an algorithm with runtime , where is the number of required objects plus the number of objects with nonzero penalty. Similarly, the technique of homology covers, by Chambers, Erickson, Fox, and Nayyeri [8], is applicable, but yields algorithms with runtime or , thus again with an exponential dependence on . If there are many objects with nonzero penalty, our algorithm with runtime is faster.
Specifying only the number of objects to be enclosed.
If we are just given a set of points in general position and the exact number of points to be enclosed, a minimum-perimeter polygon enclosing at least points is convex, contains exactly points, and can be found in polynomial time by an algorithm of Eppstein, Overmars, Rote, and Woeginger [12, Corollary 5.3, Case 3]. This algorithm could for example be used to identify an unusual cluster in an otherwise uniformly distributed point set. However, if the input consists of polygons instead of points, we are not aware of a better method than guessing the polygons to be enclosed and applying our main result, resulting in an algorithm of running time if there are objects.
More variations.
Some related separation and enclosure problems have been recently studied. Abrahamsen, Giannopoulos, Löffler, and Rote [1] investigated the problem of separating two or more groups of polygonal objects by a shortest system of fences. These fences may form an arbitrary plane graph, not necessarily a cycle. For separating two groups of polygons by a shortest fence, there is an algorithm of running time , based on minimum-cut techniques [1]. For separating more than two groups, only approximation algorithms are known. While we study a problem in the same spirit, a key difference is that we require a single (weakly) simple cycle, which makes the techniques of this article not applicable for us.
Chan, He, and Xue [9] studied the problem of choosing a smallest subset of objects from a given set whose union encloses a given point set. For this problem, there are only approximation algorithms. Klost, van Kreveld, Perz, Rote, and Tkadlec [13] have recently investigated optimum “blob-trees”, where the objective is to connect a set of points by a combination of curves and edges.
2 Preliminaries
2.1 Weakly simple polygons
A polygon is weakly simple if it has fewer than three vertices, or it has at least three vertices and for any , the vertices can be perturbed by at most to yield a simple polygon [2, 10]. We traverse a weakly simple polygon counterclockwise, i.e., with the interior to the left of each edge. Our proof uses a combinatorial characterization of a weakly simple polygon in terms of a non-crossing Euler tour in a plane multigraph [5, Lemma 16 in Appendix A]. This allows us to partition the edges of a weakly simple polygon into boundary walks of interior faces, see Figure 3. Note that we first subdivide an edge when a vertex lies in its interior.
A vertex of a weakly simple polygon with incoming edge and outgoing edge is a transition vertex if and belong to different interior faces. An interior face of two edges is a corridor and an interior face of more than two edges is a chamber. A chamber is not necessarily a simple polygon, but it is almost simple (see Figure 3(b)). More formally, a bounded almost-simple polygon is the boundary walk of an interior face of a connected straight-line graph drawing in the plane. We also allow an unbounded almost-simple polygon by traversing the boundary of the outer face clockwise. An almost-simple polygon has a connected interior and a bounded almost-simple polygon can be triangulated. Almost-simple polygons play two roles: the bounded ones arise as chambers; and our general Enclosure-with-Penalties problem allows almost-simple input polygons (including a single unbounded one).
All these concepts are made rigorous in [5, Appendix A]. We note that the partition of the edges of a weakly simple polygon into interior faces (and hence the definition of corridors and transition vertices) is not unique, see Figure 3(c). This non-uniqueness, which is inherent in the -approximation definition of weakly simple polygons, does not affect our proofs.
2.2 Winding number and winding parity
Our algorithm will construct intermediate polygons that are not necessarily weakly simple; so it will be useful to generalize “enclosed by” in terms of winding numbers. For a polygon and a point not lying on a vertex or edge of , the winding number of with respect to is defined as follows. Take a ray from that avoids vertices of . If an edge of crosses from right to left, we count this as ; a crossing from left to right is counted as , and the total count gives the winding number. This is well-defined independent of the choice of . The winding number is undefined for points on . Observe that, for a weakly simple polygon traversed counterclockwise, point lies in the interior of if and only if . The winding parity of with respect to is .
3 Our Common Framework: Enclosure-with-Penalties
In this section we formally define the
Enclosure-with-Penalties problem that provides a common
framework for both the geometric and graph settings.
Input:
-
A set of interior-disjoint almost-simple polygons in the plane. We allow a single polygon to be unbounded. We subdivide polygon edges to ensure that no polygon vertex lies in the interior of an edge of another polygon. The free space is the plane minus the interiors of the polygons.
-
A partition of the input polygons into a set of required polygons and the remaining set of optional polygons. If there is an unbounded polygon, it must lie in .
-
For each polygon , a penalty .
-
The weight of a line segment in the free space is its Euclidean length, except for squeezed edges. A squeezed edge is a polygon edge that is incident to polygons on both sides. We may specify an arbitrary positive weight for a squeezed edge. Subsegments of a squeezed edge get proportional weight, and combinations of different squeezed or non-squeezed segments have their weights added.
Output: A weakly simple polygon that lies in the free space and contains all polygons of while minimizing the cost , which is defined as
(1) |
where is the sum of the weights of the edges of , and is the sum of the penalties of the polygons of that are inside . Our main result is:
Theorem 3.
Enclosure-with-Penalties for required polygons can be solved in time and space, if the input polygons have vertices in total.
Theorem 1 is an immediate consequence of Theorem 3. Theorem 2 follows from Theorem 3 via a straight-line embedding of the graph, as outlined in Section 1 and detailed in the full version [5, Appendix B].
The Enclosure-with-Penalties problem as defined above does not allow point objects. (They are not almost-simple.) [5, Appendix I] shows how to deal with point objects.
4 Dynamic Programming Algorithm
The algorithm builds a polygon composed of free-space edges, where a free-space edge is an inclusionwise minimal line segment in the free space whose endpoints are vertices of the input polygons. We prove in Section 6 that this restriction to free-space edges is valid. We refer to a solution interchangeably as a polygon or as a closed walk in the graph of free-space edges.
The intuition for the algorithm is based on the decomposition of a weakly simple polygon into corridors and chambers joined at “cutpoints”, see Figure 3. A cutpoint separates into subpolygons and partitions the set of enclosed objects. Our first type of subproblem finds polygons that enclose a specified subset of and go through a specified vertex.
A corridor is a digon, and a chamber can be triangulated by adding chords, where a chord may cut through polygons. We therefore use digons and triangles as the basic building blocks to construct our solutions. A chord cuts off part of the solution. Our second type of subproblem finds polygons that use a walk of free-space edges between two given vertices and together with the chord (called the mouth) to enclose a specified subset of .
Since a mouth may cut through polygons, we choose a reference point in the interior of every input polygon , and aim to enclose for . Observe that a weakly simple polygon in the free space encloses if and only if lies in the interior of .
The dynamic program explicitly keeps track of the subset of required objects that are enclosed by partial solutions ( possibilities). However, when combining two partial solutions, the algorithm does not have enough information to check whether they cross. Thus, we allow self-crossing solutions. In particular, our use of the word “enclosing” is aspirational, and will only be made precise in terms of winding numbers, see Section 4.2. When we state the algorithm, we invite the reader to think of a weakly simple solution without crossings.
Types of subproblems.
A subproblem of type (“closed”) is rooted at a vertex , and we build a closed walk that goes through and is composed of free-space edges. A subproblem of type (“mouth”) is rooted at a segment between vertices of input polygons, called the mouth, and we build an open walk of free-space edges from to ; adding segment closes the walk. In addition to the root, each subproblem has two more parameters, and : The set specifies the precise subset of required objects that must be enclosed, and the integer is an upper bound on the number of edges of the walk. In each case, the subproblem looks for a minimum-cost solution with the required properties.
4.1 Dynamic programming recursion
We now give recursive formulas for and , preceded in each case by an explanation of the formulas. The formulas with the respective partitions of the walk are illustrated in Figure 4.
For we have two base cases: if , then the shortest closed walk is just the point and its cost is (Equation (2)); and if and , there is no solution, and we set the cost to (Equation (3)). Otherwise we have two general cases: the closed walk uses an edge of the free space (for some ) plus a solution (Equation (4)); or the closed walk is composed of two smaller closed walks that both go through (Equation (5)). The notation means disjoint union: we partition the objects in into two sets, each “enclosed” by exactly one of the two closed walks.
The base cases define for and for :
(2) | ||||
(3) |
In the general case, for and , we set
(4) | ||||
(5) |
For there are two possibilities: if is a free-space edge, we can use a closed walk at plus the edge (Equation (6)); or we can attach a triangle to the mouth (Equation (7)). In the first case we add the weight of the edge . In the triangle case we take into account the polygons with reference points in , where we consider to be closed on and and open on , and we define to be the sum of the penalties of polygons of with reference points in .
is defined only for :
(6) | ||||
(7) | ||||
As we shall see later in Lemma 13, the optimal walk has at most edges. Thus, we define the solution to the whole problem as
(8) |
When we allow point objects, the algorithm needs a few refinements, see [5, Appendix I]. In the following sections we prove that is the correct value. Although not required by our proof, we note for completeness in [5, Appendix L] that the class of polygons over which the algorithm optimizes is the class of immersed or self-overlapping weakly simple polygons.
Runtime and Space.
4.2 Extracting the solution
With every finite value computed in the dynamic program we can naturally associate an open or closed walk of free-space edges that has this value as its cost (with “partially enclosed” objects taken into account according to their reference points): Figure 4 illustrates how each value is computed from the values of subproblems; the walks corresponding to those subproblems are composed accordingly. (For more details, see [5, Appendix C.2].) We will prove in Section 6 that is finite; so the associated closed walk exists:
Definition 4.
is the polygon associated with the optimum solution value in (8).
The polygon uses free-space edges, but it might not be weakly simple, and there is no notion of enclosed objects. Instead, we use winding numbers: we show that the reference point of any object in has winding number 1 in , and we define a cost measure for in terms of winding numbers and prove equality with .
Definition 5.
For any polygon in the free space, define the cost to be
When is a counterclockwise weakly simple polygon, this matches the previous definition , see Equation (1). The solution produced by the algorithm has the following properties:
Lemma 6.
-
(A)
;
-
(B)
for all , ;
-
(C)
for all points that do not lie on , .
Lemma 6 is proved in [5, Appendix C.2] by induction as the dynamic program builds solutions by gluing together open/closed walks. The induction must apply also to open walks, and we use the fact that winding numbers add when gluing walks together, see Figure 5.
5 Uncrossing Algorithm and Final Output
The final step of our algorithm “uncrosses” the closed walk produced by the dynamic program and turns it into a weakly simple polygon without increasing the cost. To do so, we cut it into subpaths, eliminate some, and reorder the rest.
Our algorithm uses a known result about taking a plane multigraph (specified via its rotation system) and finding a non-crossing Euler tour in which successive visits to a vertex do not cross each other. (See [5, Appendix A] for more detailed definitions.) The existence of such a tour in an Eulerian plane multigraph is an easy exercise, see [17] or [18, Lemma 3.1], and a linear-time algorithm was given by Akitaya and Tóth [3]. We summarize it in the following proposition, and give a self-contained proof in [5, Appendix D].
Proposition 7 (Uncrossing Eulerian plane multigraphs).
Given a plane connected Eulerian multigraph with edges, specified by its combinatorial map, we can, in time, compute a non-crossing Euler tour of .
We now sketch our algorithm to uncross any polygon to a weakly simple polygon . An interior crossing is a point that is in the relative interiors of two (or more) edges that are not collinear. A fork (or interior vertex) is a vertex in the relative interior of an edge.
Algorithm 8 (Uncrossing Algorithm).
-
1.
Subdivide every edge of at every fork and interior crossing.
-
2.
In the resulting multiset of edges (line segments in the plane) reduce multiplicities to or by repeatedly discarding pairs of equal line segments. The result is a plane connected Eulerian multigraph.
-
3.
Apply Proposition 7 to find a non-crossing Euler tour. This corresponds to a weakly simple polygon .
In the full version of our paper [5, Appendix D], we give further details of the algorithm and an implementation with runtime where is the number of edges of and is the number of interior crossings of (with multiple crossings counted once). For input we show that there are no interior crossings, so the runtime is .
We use the following important property of the Uncrossing Algorithm. Recall the definition of winding parity from Section 2.2.
Lemma 9.
Every point in the plane that does not lie on has the same winding parity in and in .
Proof.
For any ray from to infinity that avoids vertices of , the parity of the number of edges it crosses is the same for and since we have discarded pairs of equal line segments. The direction in which traverses an edge does not affect the winding parity. ( and have the same parity.)
Definition 10.
is the output of the Uncrossing Algorithm on input , oriented in counterclockwise direction.
Lemma 11.
is a weakly simple polygon in the free space. encloses and .
Proof.
Consider a polygon . By Lemma 6(B), . By Lemma 9, has the same winding parity in . Since is weakly simple, every point has winding number or . Thus and encloses .
Next we consider costs. The definition of the costs in Equation (1) gives
where is the sum of the penalties of objects of enclosed by .
By Lemma 6(A) and the definition of ,
The Uncrossing Algorithm ensures that . It remains to compare the penalties. Let be a polygon of enclosed by , i.e., with . By Lemma 9, the reference point has the same winding parity in , and by Lemma 6(C), . Thus and
Therefore . (In fact, equality holds, as shown in the next section.)
6 Correctness Proof
In defining , we relied on the assumption that is finite. In this section we prove this fact, which implies that exists, and we prove our main correctness result:
Theorem 12.
is an optimum solution to the Enclosure-with-Penalties problem.
We defined the Enclosure-with-Penalties problem over the continuous space of all weakly simple polygons, but our algorithm only explores the discrete space of weakly simple polygons composed of at most free-space edges. So we first prove that there is an optimum solution in this discrete space. A feasible solution is a weakly simple polygon that lies in the free space and encloses .
Lemma 13.
For the Enclosure-with-Penalties problem, there exists an optimum solution of finite cost that consists of at most free-space edges.
Proof idea (Details in [5, Appendix E]).
Let be the discrete set of feasible solutions that consist of free-space edges each traversed at most twice. Because a planar graph on vertices has at most edges, any solution in has at most free-space edges.
We next prove that contains a feasible solution that encloses and excludes , and thus has finite cost. The idea is to take the cycle boundaries of polygons in and join them by paths traversed twice.
Since is finite and nonempty, this implies that, among the solutions in , there is a solution of minimum cost.
Finally, we prove that any feasible solution not in can be homotopically shortened and then uncrossed to get a solution in of no greater cost. Thus is an optimum solution.
We prove that the solution from Lemma 13 is one of the candidate solutions over which the dynamic program optimizes. As a consequence:
Lemma 14.
.
Theorem 12 then follows: Lemmas 13 and 14 establish that is finite. Thus exists. By Lemma 11, is a feasible solution and . Combining with Lemma 14 yields . Thus is optimal.
We say a few words about the proof of Lemma 14. By the definition of , it suffices to show that for a vertex on . We give an inductive proof of the more general statement that is at most the cost of any weakly simple polygon with at most free-space edges that encloses and goes through . Since has at most edges, this implies 14. The following lemma, which is proved in [5, Appendix E], includes an analogous inductive statement for , with a suitable definition of the cost of an open walk . It refers to transition vertices, which were defined in Section 2.1.
Lemma 15.
(A) Let be a weakly simple polygon with free-space edges, going through vertex , and let be the objects of that are enclosed by . Then, for all , .
(B) Let be an open walk with free-space edges from to such that the polygon is weakly simple and is not a transition vertex of . Let be the objects of whose reference points lie inside and not on . Then, for all , .
7 Reducing the Runtime with a Dijkstra-Style Algorithm
The runtime of our algorithm to solve the Enclosure-with-Penalties problem can be reduced by a factor, leading to the bound of Theorem 3.
The dynamic programming algorithm in Section 4 is guided by a parameter , which limits the number of edges of the walk. We have proved (Lemma 13) that there is an optimal solution with at most edges. Hence, the solution cannot be improved by allowing larger values of ; the iteration stabilizes, and the algorithm can stop when reaches . The parameter has been useful for ensuring that the quantities in the dynamic programming algorithm are well-defined, and it is essential as an induction variable for the proofs. We will now eliminate and solve the recursion in the style of Dijkstra’s algorithm for shortest paths. In particular, we use a generalization of Dijkstra’s algorithm as proposed by Knuth [14].
More specifically, we define and in terms of the quantities from Section 4. By the above observations, and for all . Therefore, the limit quantities and fulfill a variation of the recursions 2–7 where the parameter is eliminated:
(9) | ||||
(10) | ||||
(11) | ||||
(12) | ||||
(13) | ||||
(14) | ||||
(15) | ||||
As in Equation (8), we define the solution to the whole problem as
(16) |
By Lemma 13 and by the definition of and , the value of resulting from (16) is the same as the one resulting from (8).
The system 9–15 is a system of equations that involves cyclic dependencies. Nevertheless, we can show that it has a unique solution [5, Appendix F.1, Lemma 22]. The reason is that on the right-hand side of the equations, the result of any expression combining some quantities of the form and is always larger than these quantities.
Similar to Dijkstra’s shortest-path algorithm, our algorithm maintains tentative values and . The smallest of the tentative values is made permanent, and all right-hand side expressions where this value appears are evaluated and used to update the corresponding tentative left-hand side values. The algorithm that carries out this idea is shown in the full version [5, Appendix F.2, Algorithm 1].
The most numerous quantities are the values , and hence the space complexity is . Compared to the running time for the dynamic programming algorithm in Section 4, we save a factor : The elimination of reduces the number of recursions by a factor , and we save another factor because we need not go through all decompositions on the right-hand side. The analysis of the full algorithm is given in [5, Appendix F.3]. The total running time is , as claimed in Theorem 3.
8 The Inverted Problem
In the inverted problem, the required objects have to be outside the weakly simple polygon , and the penalties of the polygons that are outside are counted (see the introduction). The approach for the original problem has to be adapted accordingly. To derive a suitable dynamic programming formulation, we decompose the outside of into elementary pieces, as shown in Figure 6: We form the convex hull of and extend vertical rays upward and downward from the convex hull vertices. This leads to two additional types of regions:
-
a left and a right half-plane, each bounded by a vertical line through an object vertex;
-
vertical planks, that is, regions bounded by a line segment and two vertical upward rays or two vertical downward rays. We discuss such regions in [5, Appendix F.4].
We stick to the convention that the interior of the region of interest lies on the left side of . Accordingly, the solution polygon is now oriented clockwise.
In the algorithm, we build the region of interest outside-in, see Figure 7, starting from a left half-plane bounded by two vertical rays through an object vertex. We add planks from left to right along common rays, and, as in Section 4, we may also attach triangles along common edges and digons along common vertices. In addition to the usual bounded walks, we now also consider polygonal walks that start from the endpoint of a vertical downward ray and end at a vertical upward ray. More precisely, for each pair of vertices , we consider a subproblem of type (“unbounded”), which considers regions bounded by a vertical ray down from , a walk from to , and a vertical ray up from , see Figure 7 for an example; is allowed. Accordingly, the algorithm computes quantities for all and . The two unbounded rays jointly play the role of the mouth.
9 Applications, Extensions, and Open Problems
Splitting a surface.
Our result may shed some light on the following open problem by Bulavka, Colin de Verdière, and Fuladi [6, Conclusion]: given an orientable combinatorial surface of genus , and an integer , , is it FPT in to compute a shortest weakly simple closed curve that cuts off a surface of genus ? The problem is FPT in [7, Theorem 6.1]. Our algorithm for Graph-Enclosure-with-Penalties shows that the answer is yes when restricting to some (admittedly very special) instances, see [5, Appendix H], and thus provides some hope for a positive answer in general, although this remains open.
Curved objects and line segments.
We believe that our approach carries over to more general objects. Curved objects that are sufficiently well behaved can be treated by considering all bitangents as free-space edges. We can handle point objects [5, Appendix I]; line segments without other vertices in their interior should also be doable. However, extending to weakly simple polygon objects seems difficult. Even for a path object consisting of two line segments joined at point it is a challenge to prevent a solution from cutting through the path at .
Recognizing weakly simple self-overlapping polygons.
References
- [1] Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote. Geometric multicut: shortest fences for separating groups of objects in the plane. Discrete Comput. Geom., 64:575–607, 2020. doi:10.1007/s00454-020-00232-w.
- [2] Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D. Tóth. Recognizing weakly simple polygons. Discrete & Computational Geometry, 58(4):785–821, 2017. doi:10.1007/S00454-017-9918-3.
- [3] Hugo A. Akitaya and Csaba D. Tóth. Reconstruction of weakly simple polygons from their edges. International Journal of Computational Geometry & Applications, 28(02):161–180, 2018. doi:10.1142/S021819591860004X.
- [4] Esther M. Arkin, Samir Khuller, and Joseph S. B. Mitchell. Geometric knapsack problems. Algorithmica, 10(5):399–427, 1993. doi:10.1007/BF01769706.
- [5] Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote. Finding a shortest curve that separates few objects from many, April 2025. arXiv:2504.03558v1.
- [6] Denys Bulavka, Éric Colin de Verdière, and Niloufar Fuladi. Computing shortest closed curves on non-orientable surfaces. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry (SoCG 2024), volume 293 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.SoCG.2024.28.
- [7] Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Francis Lazarus, and Kim Whittlesey. Splitting (complicated) surfaces is hard. Comput. Geom., 41(1–2):94–110, 2008. doi:10.1016/j.comgeo.2007.10.010.
- [8] Erin W. Chambers, Jeff Erickson, Kyle Fox, and Amir Nayyeri. Minimum cuts in surface graphs. SIAM J. Comput., 52(1):156–195, 2023. doi:10.1137/19M1291820.
- [9] Timothy M. Chan, Qizheng He, and Jie Xue. Enclosing points with geometric objects. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry (SoCG 2024), volume 293 of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:15, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2024.35.
- [10] Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1655–1670, 2015. doi:10.1137/1.9781611973730.110.
- [11] Peter Eades and David Rappaport. The complexity of computing minimum separating polygons. Patt. Recog. Lett., 14(9):715–718, 1993. doi:10.1016/0167-8655(93)90140-9.
- [12] David Eppstein, Mark Overmars, Günter Rote, and Gerhard Woeginger. Finding minimum area -gons. Discrete Comp. Geom., 7:45–58, 1992. doi:10.1007/BF02187823.
- [13] Katharina Klost, Marc van Kreveld, Daniel Perz, Günter Rote, and Josef Tkadlec. Minimum spanning blob-trees. In Jan Kratochvíl and Giuseppe Liotta, editors, Abstracts of the 41st European Workshop on Computational Geometry (EuroCG 2025), April 9–11, Liblice, Czech Republic, pages 23:1–23:8, 2025. doi:10.48550/arXiv.2503.02439.
- [14] Donald E. Knuth. A generalization of Dijkstra’s algorithm. Information Processing Letters, 6(1):1–5, 1977. doi:10.1016/0020-0190(77)90002-3.
- [15] Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk. On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. In Proc. 59th Ann. IEEE Symp. Foundat. Comput. Sci. (FOCS), pages 474–484, 2018. doi:10.1109/FOCS.2018.00052.
- [16] Peter W. Shor and Christopher J. Van Wyk. Detecting and decomposing self-overlapping curves. Comput. Geom.: Theory and Applications, 2(1):31–50, 1992. doi:10.1016/0925-7721(92)90019-O.
- [17] David Singmaster and Jerrold W. Grossman. Solution to problem E2897: An Eulerian circuit with no crossings. The American Mathematical Monthly, 90(4):287–288, 1983. doi:10.2307/2975767.
- [18] Mu-Tsun Tsai and Douglas B. West. A new proof of 3-colorability of Eulerian triangulations. Ars Mathematica Contemporanea, 4:73–77, 2011. doi:10.26493/1855-3974.193.8e7.