Let G be a complete edge-weighted graph on n vertices. To each subset of vertices of G assign the cost of the minimum spanning tree of the subset as its weight. Suppose that n is a multiple of some fixed positive integer k . The k -matching problem is the problem of finding a partition of the vertices of G into k -sets (sets of k elements), that minimizes the sum of the weights of the k -sets. The case of k = 3 has been shown to be NP-hard [Johnsson et al., 1998]. In the Euclidean version, the vertices of G are points in the plane and the weight of an edge is the Euclidean distance between its endpoints. We call this problem the Euclidean k -matching problem. We show that, for every fixed k ≥ 3 , the Euclidean k -matching problem is NP-hard. This resolves an open problem in the literature and provides the first theoretical justification for the use of known heuristic methods in the case of k = 3 . We also show that the problem remains NP-hard if the trees are required to be paths.

Abstract We explore an extension to rectilinear convexity of the classic problem of computing the convex hull of a set of geometric objects. Namely, we solve the problem of computing the rectilinear convex hull with arbitrary orientation for a set of segments and circles. We describe efficient algorithms to compute and maintain the objects appearing on the boundary of the rectilinear convex hull of such sets, while we rotate the coordinate axes by an angle that goes from 0 to $$2\pi $$ 2 π . We first consider a set of n segments. If the segments are not necessarily disjoint, we describe an algorithm that runs in optimal $$\Theta (n\log n)$$ Θ ( n log n ) time and $$O(n\alpha (n))$$ O ( n α ( n ) ) space, where $$\alpha (n)$$ α ( n ) is the extremely slowly growing inverse of Ackermann’s function. If instead the segments form a simple polygonal chain, we describe an algorithm that improves the previous space complexity to $$\Theta (n)$$ Θ ( n ) . We then extend the techniques used in these algorithms to a set of n circles. The resulting algorithm runs in optimal $$\Theta (n\log n)$$ Θ ( n log n ) time and $$\Theta (n)$$ Θ ( n ) space.

Abstract Let P be a set of n points in $$\mathbb {R}^3$$ R 3 in general position, and let RCH(P) be the rectilinear convex hull of P. In this paper we obtain an optimal $$O(n\log n)$$ O ( n log n ) time and O(n) space algorithm to compute RCH(P). We also obtain an efficient $$O(n\log ^2 n)$$ O ( n log 2 n ) time and $$O(n\log n)$$ O ( n log n ) space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of P as we rotate $${\mathbb {R}}^3$$ R 3 around the Z-axis. We study some combinatorial properties of the rectilinear convex hulls of point sets in $$\mathbb {R}^3$$ R 3 . Finally, as an application of the obtained results, we show an approximation algorithm to an optimization fitting problem in $$\mathbb {R}^3$$ R 3 .

Abstract Huemer et al. (Discrete Mathematics, 2019) proved that for any two point sets R and B with $$|R|=|B|$$ | R | = | B | , the perfect matching that matches points of R with points of B, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a common point. Each pair of matched points $$p\in R$$ p ∈ R and $$q\in B$$ q ∈ B induces the disk of smallest diameter that covers p and q. Following this research line, in this paper we consider the perfect matching that maximizes the total Euclidean distance. First, we prove that this new matching for R and B does not always ensure the common intersection property of the disks. Second, we extend the study of this new matching for sets of 2n uncolored points in the plane, where a matching is just a partition of the points into n pairs. As the main result, we prove that in this case all disks of the matching do have a common point.

Abstract Let S be a set of n points in general position in the plane, and let $$X_{k,\ell }(S)$$ X k , ℓ ( S ) be the number of convex k-gons with vertices in S that have exactly $$\ell $$ ℓ points of S in their interior. We prove several equalities for the numbers $$X_{k,\ell }(S)$$ X k , ℓ ( S ) . This problem is related to the Erdős–Szekeres theorem. Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points. Analogous results for higher dimension are shown as well.

Abstract Given a finite set of weighted points in $${\mathbb {R}}^d$$ R d (where there can be negative weights), the maximum box problem asks for an axis-aligned rectangle (i.e., box) such that the sum of the weights of the points that it contains is maximized. We consider that each point of the input has a probability of being present in the final random point set, and these events are mutually independent; then, the total weight of a maximum box is a random variable. We aim to compute both the probability that this variable is at least a given parameter, and its expectation. We show that even in $$d=1$$ d = 1 these computations are #P-hard, and give pseudo-polynomial time algorithms in the case where the weights are integers in a bounded interval. For $$d=2$$ d = 2 , we consider that each point is colored red or blue, where red points have weight $$+1$$ + 1 and blue points weight $$-\infty $$ - ∞ . The random variable is the maximum number of red points that can be covered with a box not containing any blue point. We prove that the above two computations are also #P-hard, and give a polynomial-time algorithm for computing the probability that there is a box containing exactly two red points, no blue point, and a given point of the plane.

Let $P$łabelpage1 be a set of $n$ points in the plane. We consider a variation of the classical Erdös--Szekeres problem, presenting efficient algorithms with $O(n^3)$ running time and $O(n^2)$ space complexity that compute (1) a subset $S$ of $P$ such that the boundary of the rectilinear convex hull of $S$ has the maximum number of points from $P$, (2) a subset $S$ of $P$ such that the boundary of the rectilinear convex hull of $S$ has the maximum number of points from $P$ and its interior contains no element of $P$, (3) a subset $S$ of $P$ such that the rectilinear convex hull of $S$ has maximum area and its interior contains no element of $P$, and (4) when each point of $P$ is assigned a weight, positive or negative, a subset $S$ of $P$ that maximizes the total weight of the points in the rectilinear convex hull of $S$. We also revisit the problems of computing a maximum area orthoconvex polygon and computing a maximum area staircase polygon, amidst a point set in a rectangular domain. We obtain new and simpler algorithms to solve both problems with the same complexity as in the state of the art.

In 2001, Karolyi, Pach and Toth introduced a family of point sets to solve an Erdos-Szekeres type problem; which have been used to solve several other Edos-Szekeres type problems. In this paper we refer to these sets as nested almost convex sets. A nested almost convex set X has the property that the interior of every triangle determined by three points in the same convex layer of X , contains exactly one point of X . In this paper, we introduce a characterization of nested almost convex sets. Our characterization implies that there exists at most one (up to order type) nested almost convex set of n points. We use our characterization to obtain a linear time algorithm to construct nested almost convex sets of n points, with integer coordinates of absolute values at most O(n log 25). Finally, we use our characterization to obtain an O (n logn)-time algorithm to determine whether a set of points is a nested almost convex set.

Given a set | $P$ | of | $n$ | points in the plane, we study the computation of the probability distribution function of both the area and perimeter of the convex hull of a random subset | $S$ | of | $P$ | . The random subset | $S$ | is formed by drawing each point | $p$ | of | $P$ | independently with a given rational probability | $\pi _p$ | . For both measures of the convex hull, we show that it is #P-hard to compute the probability that the measure is at least a given bound | $w$ | . For | $ \varepsilon \in (0,1)$ | , we provide an algorithm that runs in | $O(n^{6}/ \varepsilon )$ | time and returns a value that is between the probability that the area is at least | $w$ | , and the probability that the area is at least | $(1- \varepsilon )w$ | . For the perimeter, we show a similar algorithm running in | $O(n^{6}/ \varepsilon )$ | time. Finally, given | $ \varepsilon ,\delta \in (0,1)$ | and for any measure, we show an | $O(n\log n+ (n/ \varepsilon ^2)\log (1/\delta ))$ | -time Monte Carlo algorithm that returns a value that, with probability of success at least | $1-\delta $ | , differs at most | $ \varepsilon $ | from the probability that the measure is at least | $w$ | .

Imagine a wooden plate with a set of non-overlapping geometric objects painted on it. How many of them can a carpenter cut out using a panel saw making guillotine cuts, i.e., only moving forward through the material along a straight line until it is split into two pieces? Already fifteen years ago, Pach and Tardos investigated whether one can always cut out a constant fraction if all objects are axis-parallel rectangles. However, even for the case of axis-parallel squares this question is still open. In this paper, we answer the latter affirmatively. Our result is constructive and holds even in a more general setting where the squares have weights and the goal is to save as much weight as possible. We further show that when solving the more general question for rectangles affirmatively with only axis-parallel cuts, this would yield a combinatorial O(1)-approximation algorithm for the Maximum Independent Set of Rectangles problem, and would thus solve a long-standing open problem. In practical applications, like the mentioned carpentry and many other settings, we can usually place the items freely that we want to cut out, which gives rise to the two-dimensional guillotine knapsack problem: Given a collection of axis-parallel rectangles without presumed coordinates, our goal is to place as many of them as possible in a square-shaped knapsack respecting the constraint that the placed objects can be separated by a sequence of guillotine cuts. Our main result for this problem is a quasi-PTAS, assuming the input data to be quasi-polynomially bounded integers. This factor matches the best known (quasi-polynomial time) result for (non-guillotine) two-dimensional knapsack.

The Swap-Insert Correction distance from a string S of length n to another string L of length $$m\ge n$$ on the alphabet [1..d] is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting S into L. Contrarily to other correction distances, computing it is NP-Hard in the size d of the alphabet. We describe an algorithm computing this distance in time within $$O(d^2 nm g^{d-1})$$ , where there are $$n_\alpha $$ occurrences of $$\alpha $$ in S, $$m_\alpha $$ occurrences of $$\alpha $$ in L, and where $$g=\max _{\alpha \in [1..d]} \min \{n_\alpha ,m_\alpha -n_\alpha \}$$ measures the difficulty of the instance. The difficulty g is bounded by above by various terms, such as the length of the shortest string S, and by the maximum number of occurrences of a single character in S. The latter bound yields a running time within $$O(d(n+m)+(d/(d-1)^{d-2})\cdot n^{d}(m-n))$$ in the worst case over instances of fixed lengths n and m for S and L, which further simplifies to within $$O(n^d(m-n)+m)$$ when d is fixed, the state of the art for this problem. This illustrates how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario.

Consider a set of receptors belonging to two competitive telecommunication firms, the blue firm and the red firm. The receptors are represented as points in the plane, b are blue and belong to the blue firm and r are red and belong to the red firm. The blue firm has an emitting device represented as a point that moves along a path sending information to blue receptors as follows: At any time, the device sends information to all blue receptors covered by the largest disk centered at it and contains no red receptor. In this scenario, we study two optimization problems. The first problem is to compute a path, P, such that the number of blue receptors served by a moving device is maximized. In particular, we give efficient algorithms when P is a straight line, an anchored half-line and an axis-parallel double ray. As a second task, we study the problem of removing the minimum number of red receptors in such a way that there exists a straight line path P so that if the device moves along P all blue receptors are served. We prove geometrical properties of an optimal straight line and propose efficient algorithms depending on the degrees of freedom of the line.