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 We explore the separability of point sets in the plane by a restricted-orientation convex hull, which is an orientation-dependent, possibly disconnected, and non-convex enclosing shape that generalizes the convex hull. Let R and B be two disjoint sets of red and blue points in the plane, and $$\mathcal {O}$$ O be a set of $$k\ge 2$$ k ≥ 2 lines passing through the origin. We study the problem of computing the set of orientations of the lines of $$\mathcal {O}$$ O for which the $$\mathcal {O}$$ O -convex hull of R contains no points of B. For $$k=2$$ k = 2 orthogonal lines we have the rectilinear convex hull. In optimal $$O(n\log n)$$ O ( n log n ) time and O(n) space, $$n = \vert R \vert + \vert B \vert $$ n = | R | + | B | , we compute the set of rotation angles such that, after simultaneously rotating the lines of $$\mathcal {O}$$ O around the origin in the same direction, the rectilinear convex hull of R contains no points of B. We generalize this result to the case where $$\mathcal {O}$$ O is formed by $$k \ge 2$$ k ≥ 2 lines with arbitrary orientations. In the counter-clockwise circular order of the lines of $$\mathcal {O}$$ O , let $$\alpha _i$$ α i be the angle required to clockwise rotate the ith line so it coincides with its successor. We solve the problem in this case in $$O({1}/{\Theta }\cdot N \log N)$$ O ( 1 / Θ · N log N ) time and $$O({1}/{\Theta }\cdot N)$$ O ( 1 / Θ · N ) space, where $$\Theta = \min \{ \alpha _1,\ldots ,\alpha _k \}$$ Θ = min { α 1 , … , α k } and $$N=\max \{k,\vert R \vert + \vert B \vert \}$$ N = max { k , | R | + | B | } . We finally consider the case in which $$\mathcal {O}$$ O is formed by $$k=2$$ k = 2 lines, one of the lines is fixed, and the second line rotates by an angle that goes from 0 to $$\pi $$ π . We show that this last case can also be solved in optimal $$O(n\log n)$$ O ( n

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.

Given a set S of regions with piece-wise linear boundary and a positive angle α < 90°, we consider the problem of computing the locations and orientations of the minimum number of α-floodlights positioned at points in S which suffice to illuminate the entire x-axis. We show that the problem can be solved in O(n log n) time and O(n) space, where n is the number of vertices of the set S.

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.

A set of vertices S resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. This paper studies the metric dimension of cartesian products $G\,\square\,H$. We prove that the metric dimension of $G\,\square\,G$ is tied in a strong sense to the minimum order of a so‐called doubly resolving set in G. Using bounds on the order of doubly resolving sets, we establish bounds on $G\,\square\,H$ for many examples of G and H. One of our main results is a family of graphs G with bounded metric dimension for which the metric dimension of $G\,\square\,G$ is unbounded.