International Journal of Computational Geometry & Applications

Motivated by a crane assignment problem, we consider a Euclidean bipartite matching problem with edge-crossing constraints. Specifically, given $n$ red points and $n$ blue points in the plane, we want to construct a perfect matching between red and blue points that minimizes the length of the longest edge, while imposing a constraint that no two edges may cross each other. We show that the problem cannot be approximately solved within a factor less than 1:277 in polynomial time unless $\text{P}\text{=}\text{NP}$. We give simple dynamic programming algorithms that solve our problem in two special cases, namely (1) the case where the red and blue points form the vertices of a convex polygon and (2) the case where the red points are collinear and the blue points lie to one side of the line through the red points.

Let $P$ be a set of $n$ input points in the plane. An algorithm is proposed to place a pair of axis-parallel unit squares, either intersecting with no points in the intersection zone or disjoint, together enclosing the maximum number of input points. The time and space complexities of the algorithm are both $O\left(n^2\right)$. In case the input points are allowed to lie inside the intersection zone of two intersecting axis-parallel unit squares, two such unit squares enclosing the maximum number of input points can be placed in $O\left(n^2{\log }^{2}n\right)$ time using $O(n\log n)$ space.

Deciding 3-colorability for general plane graphs is known to be an NP-complete problem. However, for certain families of graphs, like triangulations, polynomial time algorithms exist. We consider the family of pseudo-triangulations, which are a generalization of triangulations, and prove NP-completeness for this class. This result also holds if we bound their face degree to four, or exclusively consider pointed pseudo-triangulations with maximum face degree five. In contrast to these completeness results, we show that pointed pseudo-triangulations with maximum face degree four are always 3-colorable. An according 3-coloring can be found in linear time. Some complexity results relating to the rank of pseudo-triangulations are also given.

A variation on the classical polygon illumination problem was introduced in [Aichholzer et al. EuroCG’09]. In this variant light sources are replaced by wireless devices called $k$-modems, which can penetrate a fixed number $k$, of “walls”. A point in the interior of a polygon is “illuminated” by a $k$-modem if the line segment joining them intersects at most $k$ edges of the polygon. It is easy to construct polygons of $n$ vertices where the number of $k$-modems required to illuminate all interior points is $\Omega (n/k)$. However, no non-trivial upper bound is known. In this paper we prove that the number of kmodems required to illuminate any polygon of $n$ vertices is $O(n/k)$. For the cases of illuminating an orthogonal polygon or a set of disjoint orthogonal segments, we give a tighter bound of $4n/k+5/3$. Moreover, we present an $O(n\log n)$ time algorithm to achieve this bound.