We study the watchman route problem for a set of two watchmen for the objective of minimizing the length of the longest route (min-max) inside a simple polygon P having n vertices, which is known to be weakly NP-hard. First, we consider seeing a discrete set of m points in the interior of P. We show that even this problem is weakly NP-hard and present an approximation algorithm with approximation ratio 2 + ε that runs in O(m5n) time, assuming that a starting point for each of the two routes is given. We generalize the algorithm to see all of the interior of P in O(n6) time with approximation ratio 2 + π/2 ≈ 3.571, improving on the previously known best algorithm that has an approximation ratio of ≈ 6.922 and runtime O(n2) [8]. Finally, we describe how to extend this algorithm to the case where no starting points are given, this taking O(n8) time, yielding an approximation ratio of 3 + π/2 ≈ 4.571, improving on the previously known best approximation algorithm with ratio ≈ 5.969 also having runtime O(n8) [8].

We study the problem of multiple anchored watchman routes, where we are given m starting points for watchmen, and aim to find routes for all watchmen such that all points in a polygon are visible from at least one route. We consider the problem in Minbar polygons,2 which are staircase polygons for which the floor of the staircase solely consists of one horizontal and one vertical edge, and in generalized Minbar polygons, which relaxes the definition of Minbar polygons, allowing for non-rectilinear edges. For Minbar polygons, we exhibit polynomial time algorithms to compute optimal solutions for both the min-max and the min-sum criteria. The min-max algorithm takes O(mlog⁡m+nlog⁡n) time, using O(m+n) storage, and the min-sum algorithm takes O(n2log⁡m+mlog⁡m) time, also using O(m+n) storage. For generalized Minbar polygons, we prove NP-hardness for the min-sum and min-max criteria, and present approximation algorithms for both criteria: an O(log⁡(m+n))-approximation taking O(m4n2) time for the min-sum criterion, and a (π+3)-approximation taking O(m3n2) time for the min-max criterion. Minbar polygons and the non-rectilinear generalization of them may seem to be very restricted polygon classes but they form an adjacent pair where the multiple anchored watchman routes problem has a polynomial time solution in one class but is NP-hard in the slightly more generalized class. It is this property that motivates our study of these restricted polygon classes.

Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon P is seen from more than one direction: we search for two routes W1, W2, such that every point p∈P is contained in a segment w1w2¯¯¯¯¯¯¯¯¯¯¯⊆P such that w1∈W1 and w2∈W2. We call such routes segment watchman routes. We show that finding the two routes that are optimal with respect to the min-max criterion is weakly NP-hard even in simple polygons, and that finding the routes that are optimal with respect to the min-sum criterion is NP-hard in polygons with holes. Moreover, we present sufficient conditions for routes to be segment watchman routes, and provide a polynomial-time 2-approximation under both the min-max criterion and the min-sum criterion, both in simple polygons. Finally, we show how to generalize our results for k watchmen.

We analyze and visualize collaboration within the Computational Geometry community by modeling co-authorship relations as a graph, where nodes correspond to individual researchers and edges represent shared publications. By aggregating and time-slicing conference data, we construct a dynamic representation of the community that supports both interactive visualization and structured search.

Given a set A of points in the plane, a family of line segments forming a matching in A is called crossing (or independent) if each pair of segments in the family intersects (or is non-intersecting, respectively). In past works, these notions have been generalized to polygons by identifying the points in A with the vertices of a given set of polygons and forbidding the line segments from intersecting or overlapping with polygon walls. In this work, we study the computational complexity of computing maximum crossing and independent families in this more general setting. As our first two results, we show that both problems are NP-hard already when the polygons are triangles. Motivated by this, we turn to parameterized algorithms. For our main algorithmic results, we consider the number of polygons on the input as the natural parameter and under this parameterization obtain a fixed-parameter algorithm for computing a largest crossing family among these polygons, and a separate XP-algorithm for computing a largest independent family that lies in one of the faces of the polygonal domain.

We initiate the study of extremal problems about faces in convex rectilinear drawings of Kn, that is, drawings where vertices are represented by points in the plane in convex position and edges by line segments between the points representing the end-vertices. We show that if a convex rectilinear drawing of Kn does not contain a common interior point of at least three edges, then there is always a face forming a convex 5-gon while there are such drawings without any face forming a convex k-gon with k≥6. A convex rectilinear drawing of Kn is regular if its vertices correspond to vertices of a regular convex n-gon. We characterize positive integers n for which regular drawings of Kn contain a face forming a convex 5-gon. To our knowledge, this type of problems has not been considered in the literature before and so we also pose several new natural open problems.

Let P be a set of n=2m+1 points in the plane in general position. We define the graph GMP whose vertex set is the set of all plane matchings on P with exactly m edges. Two vertices in GMP are connected if the two corresponding matchings have m−1 edges in common. In this work we show that GMP is connected and give an upper bound of O(n2) on its diameter. Moreover, we present a lower bound of n−2 and an upper bound of 2n−2 for the diameter of GMP for P in convex position.

We investigate saturated geometric drawings of graphs with geometric thickness k, where no edge can be added without increasing k. We establish lower and upper bounds on the number of edges in such drawings if the vertices lie in convex position. We also study the more restricted version where edges are precolored, and for k = 2 the case for vertices in non-convex position.

We consider a variant of the 2-watchmen problem that ensures that every point in a polygon P is seen from more than one direction: we search for routes W1, W2, such that for each p ∈ P there exist w1 ∈ W1, w2 ∈ W2 that see p and such that p ∈ w1w2 ⊂ P. We show that finding the two routes that are optimal with respect to the min-max criterion is NP-hard in simple polygons and present a 2-approximation algorithm for this case; moreover, we provide a polynomial-time algorithm for computing the two optimal routes with respect to the min-sum criterion in convex polygons. Finally, we discuss a generalized version of the problem with more than two watchmen.

We consider the watchman route problem for multiple watchmen in staircase polygons, which are rectilinear x- and y-monotone polygons. For two watchmen, we propose an optimal algorithm that takes quadratic time, improving on the cubic time of the trivial solution. For m ≥ 3 watchmen, we explain where our approach fails.