Abstract Given a set P of n points in $$\mathbb {R}^d$$ R d , and a positive integer $$k \le n$$ k ≤ n , the k -dispersion problem is that of selecting k of the given points so that the minimum inter-point distance among them is maximized (under Euclidean distances). Among others, we show the following: Given a set P of n points in the plane, and a positive integer $$k \ge 2$$ k ≥ 2 , the k -dispersion problem can be solved by an algorithm running in $$O\left( n^{k-1} \log {n}\right) $$ O n k - 1 log n time. This extends an earlier result for $$k=3$$ k = 3 , due to Horiyama, Nakano, Saitoh, Suetsugu, Suzuki, Uehara, Uno, and Wasa [20] to arbitrary k . In particular, it improves on previous running times for small k . Given a set P of n points in $$\mathbb {R}^3$$ R 3 , and a positive integer $$k \ge 2$$ k ≥ 2 , the k -dispersion problem can be solved by an algorithm running in $$ {\left\{ \begin{array}{ll} O\left( n^{k-1} \log {n}\right) \text {time}, & \text {if } k \text { is even};\\ O\left( n^{k-1} \log ^2{n}\right) \text {time}, & \text {if } k \text { is odd}. \end{array}\right. } $$ O n k - 1 log n time , if k is even ; O

For an ordered point set in a Euclidean space or, more generally, in an abstract metric space, the ordered Nearest Neighbor Graph is obtained by connecting each of the points to its closest predecessor by a directed edge. We show that for every set of n points in R d , there exists an order such that the corresponding ordered Nearest Neighbor Graph has maximum degree at least log ⁡ n / ( 4 d ) . Apart from the 1 / ( 4 d ) factor, this bound is the best possible. As for the abstract setting, we show that for every n -element metric space, there exists an order such that the corresponding ordered Nearest Neighbor Graph has maximum degree Ω ( log ⁡ n / log ⁡ log ⁡ n ) .

Abstract Given a set of n labeled points in general position in the plane, we remove all of its points one by one. At each step, one point from the convex hull of the remaining set is erased. In how many ways can the process be carried out? The answer obviously depends on the point set. If the points are in convex position, there are exactly n! ways, which is the maximum number of ways for n points. But what is the minimum number? It is shown that this number is (roughly) at least $$3^n$$ 3 n and at most $$12.29^n$$ 12 . 29 n .

Abstract. We consider partitions of a point set into two parts, and the lengths of the minimum spanning trees (MSTs) of the original set and of the two parts. If [Formula: see text] denotes the length of an MST of [Formula: see text], we show that every set [Formula: see text] of [Formula: see text] points admits a nontrivial bipartition [Formula: see text] for which the MST-ratio [Formula: see text] is strictly larger than 1 and that 1 is the largest number with this property. Furthermore, we provide a fast algorithm that computes such a bipartition in [Formula: see text] time and one that computes the corresponding MST-ratio in [Formula: see text] time. In certain settings, a much better MST-ratio can be guaranteed. For example, if [Formula: see text] is a set of [Formula: see text] random points uniformly distributed in [Formula: see text], then for any [Formula: see text], the MST-ratio in a maximizing partition is at least [Formula: see text] with probability tending to 1 as [Formula: see text]. Our results and techniques are extendable to higher dimensions.

A complete geometric graph consists of a set P of n points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive constant c < 1, such that every complete geometric graph on n points can be partitioned into at most cn plane graphs (that is, noncrossing subgraphs). We answer this question in the affirmative in the special case where the underlying point set P is dense, which means that the ratio between the maximum and the minimum distances in P is of the order of Θ(√n).

Abstract Let X be an n-element point set in the k-dimensional unit cube $$[0,1]^k$$ [ 0 , 1 ] k where $$k \ge 2$$ k ≥ 2 . According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour) $$x_1, x_2, \ldots , x_n$$ x 1 , x 2 , … , x n through the n points, such that $$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ ∑ i = 1 n | x i - x i + 1 | k 1 / k ≤ c k , where $$|x-y|$$ | x - y | is the Euclidean distance between x and y, and $$c_k$$ c k is an absolute constant that depends only on k, where $$x_{n+1} \equiv x_1$$ x n + 1 ≡ x 1 . From the other direction, for every $$k \ge 2$$ k ≥ 2 and $$n \ge 2$$ n ≥ 2 , there exist n points in $$[0,1]^k$$ [ 0 , 1 ] k , such that their shortest tour satisfies $$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ ∑ i = 1 n | x i - x i + 1 | k 1 / k = 2 1 / k · k . For the plane, the best constant is

We introduce the Observation Route Problem ( ORP ) defined as follows: Given a set of n pairwise disjoint obstacles (regions) in the plane, find a shortest tour (route) such that an observer walking along this tour can see (observe) each obstacle from some point of the tour. The observer does not need to see the entire boundary of an obstacle. The tour is not allowed to intersect the interior of any region (i.e., the regions are obstacles and therefore out of bounds). The problem exhibits similarity to both the Traveling Salesman Problem with Neighborhoods ( TSPN ) and the External Watchman Route Problem ( EWRP ). We distinguish two variants: the range of visibility is either limited to a bounding rectangle, or unlimited. We obtain the following results: (I) Given a family of n disjoint convex bodies in the plane, computing a shortest observation route does not admit a ( c log ⁡ n ) -approximation unless P = NP for an absolute constant c > 0 . (This holds for both limited and unlimited vision.) (II) Given a family of disjoint convex bodies in the plane, computing a shortest external watchman route is NP -hard. (This holds for both limited and unlimited vision; and even for families of axis-aligned squares.) (III) Given a family of n disjoint fat convex polygons in the plane, an observation tour whose length is at most O ( log ⁡ n ) times the optimal can be computed in polynomial time. (This holds for limited vision.) (IV) For every n ≥ 5 , there exists a convex polygon with n sides and all angles obtuse such that its perimeter is not a shortest external watchman route. This refutes a conjecture by Absar and Whitesides (2006).

A unit disk graph G on a given set P of points in the plane is a geometric graph where an edge exists between two points p,q∈P if and only if |pq|≤1. A spanning subgraph G′ of G is a k-hop spanner if and only if for every edge pq∈G, there is a path between p,q in G′ with at most k edges. We obtain the following results for unit disk graphs in the plane. Every n-vertex unit disk graph has a 5-hop spanner with at most 5.5n edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from 9n to 5.5n. Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges. Every n-vertex unit disk graph has a 2-hop spanner with O(nlog⁡n) edges. This is the first nontrivial construction of 2-hop spanners. For every sufficiently large positive integer n, there exists a set P of n points on a circle, such that every plane hop spanner on P has hop stretch factor at least 4. Previously, no lower bound greater than 2 was known. For every finite point set on a circle, there exists a plane (i.e., crossing-free) 4-hop spanner. As such, this provides a tight bound for points on a circle. The maximum degree of k-hop spanners cannot be bounded from above by a function of k for any positive integer k.

Let $P=(p_1, p_2, \dots, p_n)$ be a polygonal chain in $\mathbb{R}^d$. The stretch factor of $P$ is the ratio between the total length of $P$ and the distance of its endpoints, $\sum_{i = 1}^{n-1} |p_i p_{i+1}|/|p_1 p_n|$. For a parameter $c \geq 1$, we call $P$ a $c$-chain if $|p_ip_j|+|p_jp_k| \leq c|p_ip_k|$ for every triple $(i,j,k)$, $1 \leq i 0$, there is a noncrossing $c$-chain that has stretch factor $\Omega(n^{1/2-\varepsilon})$ for sufficiently large constant $c=c(\varepsilon)$; (ii) on the other hand, the stretch factor of a $c$-chain $P$ is $O(n^{1/2})$ for every constant $c\geq 1$, regardless of whether $P$ is crossing or noncrossing; and (iii) we give a randomized algorithm that can determine, for a polygonal chain $P$ in $\mathbb{R}^2$ with $n$ vertices, the minimum $c\geq 1$ for which $P$ is a $c$-chain in $O(n^{2.5}\ {\rm polylog}\ n)$ expected time and $O(n\log n)$ space. These results generalize to $\mathbb{R}^d$. For every dimension $d\geq 2$ and every $\varepsilon>0$, we construct a noncrossing $c$-chain that has stretch factor $\Omega(n^{(1-\varepsilon)(d-1)/d})$; on the other hand, the stretch factor of any $c$-chain is $O((n-1)^{(d-1)/d})$; for every $c>1$, we can test whether an $n$-vertex chain in $\mathbb{R}^d$ is a $c$-chain in $O(n^{3-1/d}\ {\rm polylog}\ n)$ expected time and $O(n\log n)$ space.

Given a sequence $A$ of $n$ numbers and an integer (target) parameter $1\leq i\leq n$, the (exact) selection problem asks to find the $i$-th smallest element in $A$. An element is said to be $(i,j)$-mediocre if it is neither among the top $i$ nor among the bottom $j$ elements of $S$. The approximate selection problem asks to find a $(i,j)$-mediocre element for some given $i,j$; as such, this variant allows the algorithm to return any element in a prescribed range. In the first part, we revisit the selection problem in the two-party model introduced by Andrew Yao (1979) and then extend our study of exact selection to the multiparty model. In the second part, we deduce some communication complexity benefits that arise in approximate selection. In particular, we present a deterministic protocol for finding an approximate median among $k$ players.

We construct a convex polytope of unit diameter that when placed on a horizontal surface on one of its faces, it repeatedly rolls over from one face to another until it comes to rest on some face, far away from its start position: that is, the horizontal distance between the footprints of the start and final faces can be larger than any given threshold. According to the laws of physics, the vertical distance between the center of mass of the polytope and the horizontal surface continuously decreases throughout the entire motion. The speed of the motion is irrelevant. Specifically, if the polytope is manually stopped after each tumble, the motion resumes when released (unless it stands on the final stable face). Moreover, such a polytope can be realized so that (i) it has a unique stable face, and (ii) it is an arbitrary close approximation of a unit ball. As such, this construction gives a positive answer to a question raised by Conway (1969). The arbitrarily large rolling distance property investigated here for the first time raises intriguing questions and opens new avenues for future research.

We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of n real numbers (for short, grid). First, we prove that every such grid contains a convex polygon with Omega(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d in N), and obtain a tight lower bound of Omega(log^{d-1}n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the longest convex polygonal chain in a grid that contains no two points with the same x- or y-coordinate. We show that the maximum size of such a convex polygon can be efficiently approximated up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.

Let P=(p_1, p_2, ..., p_n) be a polygonal chain. The stretch factor of P is the ratio between the total length of P and the distance of its endpoints, sum_{i = 1}^{n-1} |p_i p_{i+1}|/|p_1 p_n|. For a parameter c >= 1, we call P a c-chain if |p_ip_j|+|p_jp_k| <= c|p_ip_k|, for every triple (i,j,k), 1 <= i 0, there is a noncrossing c-chain that has stretch factor Omega(n^{1/2-epsilon}), for sufficiently large constant c=c(epsilon); (ii) on the other hand, the stretch factor of a c-chain P is O(n^{1/2}), for every constant c >= 1, regardless of whether P is crossing or noncrossing; and (iii) we give a randomized algorithm that can determine, for a polygonal chain P in R^2 with n vertices, the minimum c >= 1 for which P is a c-chain in O(n^{2.5} polylog n) expected time and O(n log n) space.

Arrangements of lines and pseudolines are fundamental objects in discrete and computational geometry. They also appear in other areas of computer science, such as the study of sorting networks. Let Bn be the number of nonisomorphic arrangements of n pseudolines and let bn = log2 Bn. The problem of estimating Bn was posed by Knuth in 1992. Knuth conjectured that and also derived the first upper and lower bounds: bn ≤ 0.7924(n2 + n) and bn ≥ n2/6 – O(n). The upper bound underwent several improvements, bn ≤ 0.6988n2 (Felsner, 1997), and bn ≤ 0.6571n2 (Felsner and Valtr, 2011), for large n. Here we show that bn ≥ cn2 – O(n log n) for some constant c > 0.2053. In particular, bn ≥ 0.2053 n2 for large n. This improves the previous best lower bound, bn ≥ 0.1887n2, due to Felsner and Valtr (2011). Our arguments are elementary and geometric in nature. Further, our constructions are likely to spur new developments and improved lower bounds for related problems, such as in topological graph drawings.

Let p1,…,pn be n distinct points in the plane, and assume that the minimum inter-point distance occurs smin times, while the maximum inter-point distance occurs smax times. It is shown that sminsmax≤98n2+O(n); this settles a conjecture of Erdős and Pach (1990).

We revisit the following problem (along with its higher dimensional variant): Given a set S of n points inside an axis-parallel rectangle U in the plane, find a maximum-area axis-parallel sub-rectangle that is contained in U but contains no points of S. 1. We prove that the number of maximum-area empty rectangles amidst n points in the plane is O(n log n 2^alpha(n)), where alpha(n) is the extremely slowly growing inverse of Ackermann's function. The previous best bound, O(n^2), is due to Naamad, Lee, and Hsu (1984). 2. For any d at least 3, we prove that the number of maximum-volume empty boxes amidst n points in R^d is always O(n^d) and sometimes Omega(n^floor(d/2)). This is the first superlinear lower bound derived for this problem. 3. We discuss some algorithmic aspects regarding the search for a maximum empty box in R^3. In particular, we present an algorithm that finds a (1-epsilon)-approximation of the maximum empty box amidst n points in O(epsilon^{-2} n^{5/3} log^2{n}) time.

We revisit the traveling salesman problem with neighborhoods (TSPN) and propose several new approximation algorithms. These constitute either first approximations (for hyperplanes, lines, and balls in R d , for d ⩾ 3) or improvements over previous approximations achievable in comparable times (for unit disks in the plane). (I) Given a set of n hyperplanes in R d , a traveling salesman problem (TSP) tour whose length is at most O (1) times the optimal can be computed in O ( n ) time when d is constant. (II) Given a set of n lines in R d , a TSP tour whose length is at most O (log 3 n ) times the optimal can be computed in polynomial time for all d . (III) Given a set of n unit balls in R d , a TSP tour whose length is at most O (1) times the optimal can be computed in polynomial time when d is constant.

The problem of finding a collection of curves of minimum total length that meet all the lines intersecting a given planar convex body was initiated by Mazurkiewicz in 1916. Such a collection forms an opaque barrier for the convex body. In 1991, Shermer proposed an exponential-time algorithm that computes an interior-restricted barrier made of segments for any given convex $n$-gon. He conjectured that the barrier found by his algorithm is optimal, but this was refuted recently by Provan et al. Here, we give a Shermer-like algorithm that computes an interior polygonal barrier whose length is at most 1.7168 times the optimal and that runs in $O(n)$ time. As a byproduct, we also deduce upper and lower bounds on the approximation ratio of Shermer's algorithm.

The problem of finding a collection of curves of minimum total length that meet all the lines intersecting a given polygon was initiated by Mazurkiewicz in 1916. Such a collection forms an opaque barrier for the polygon. In 1991 Shermer proposed an exponential-time algorithm that computes an interior-restricted barrier made of segments for any given convex n-gon. He conjectured that the barrier found by his algorithm is optimal, however this was refuted recently by Provan et al. Here we give a Shermer like algorithm that computes an interior polygonal barrier whose length is at most 1.7168 times the optimal and that runs in O(n) time. As a byproduct, we also deduce upper and lower bounds on the approximation ratio of Shermer's algorithm.

The problem of finding small sets that block every line passing through a unit square was first considered by Mazurkiewicz in 1916. We call such a set an opaque set or a barrier for the square. The shortest known barrier has length √2 + √6/2 = 2.6389.... The current best lower bound for the length of a (not necessarily connected) barrier is 2, of which the earliest record dates back to Jones in 1964. No better lower bound is known even if the barrier is restricted to lie in the square or in its close vicinity. Under a suitable locality assumption, we replace this lower bound, for barriers consisting of finitely many straight-line segments, by 2 + 10--12, which represents the first, albeit small, step in a long time toward finding the length of the shortest barrier. A sharper bound is obtained for interior barriers: the length of any interior barrier for the unit square, consisting of finitely many straight-line segments, is at least 2 + 10--5. Two of the key elements in our proofs are: (i) formulas established by Sylvester for the measure of all lines that meet two disjoint planar convex bodies, and, even more significant, (ii) a procedure for detecting lines that are witness to the invalidity of a short bogus barrier for the square.

Given a finite family of sets, Hall's classical marriage theorem provides a necessary and sufficient condition for the existence of a system of distinct representatives for the sets in the family. Here we extend this result to a geometric setting: given a finite family of objects in the Euclidean space eg, convex bodies, we highlight a sufficient condition for the existence of a system of distinct representatives for the objects that are also distant from each other. For a wide variety of geometric objects, this sufficient condition is also necessary in an asymptotic sense ie, apart from constant factors, the inequalities are best possible. Our methods are constructive and lead to efficient algorithms for computing such representatives.

We revisit the traveling salesman problem with neighborhoods (TSPN) and obtain several approximation algorithms. These constitute either improvements over previously best approximations achievable in comparable times (for unit disks in the plane), or first approximations ever (for planes, lines and unit balls in 3-space). (I) Given a set of n planes in 3-space, a TSP tour that is at most 2.31 times longer than the optimal can be computed in O(n) time. (II) Given a set of n lines in 3-space, a TSP tour that is at most O(log3 n) times longer than the optimal can be computed in polynomial time. (III) Given a set of n unit disks in the plane (resp., unit balls in 3-space), we improve the approximation ratio using a black box that computes an approximate tour for a set of points (the centers of a subset of the disks or the balls).

We obtain new lower and upper bounds for the maximum multiplicity of some weighted and, respectively, nonweighted common geometric graphs drawn on $n$ points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of $n$ points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits $\Omega (8.65^n)$ different triangulations. This improves the bound $\Omega (8.48^n)$ achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al. (ii) We obtain a new lower bound of $\Omega(12.00^n)$ for the number of noncrossing spanning trees of the double chain composed of two convex chains. The previous bound, $\Omega(10.42^n)$, stood unchanged for more than 10 years. (iii) Using a recent upper bound of $30^n$ for the number of triangulations, due to Sharir and Sheffer, we show that $n$ points in the plane in general position admit at most $O(68.62^n)$ noncrossing spanning cycles. (iv) We derive lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). We show that the number of shortest tours can be exponential in $n$ for points in general position. These tours are automatically noncrossing. Likewise, we show that the number of longest noncrossing tours can be exponential in $n$. It was known that the number of shortest noncrossing perfect matchings can be exponential in $n$, and here we show that the number of longest noncrossing perfect matchings can be also exponential in $n$. It was known that the number of longest noncrossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we re-derive tight bounds for the number of longest and shortest tours with some simpler arguments. We also give a combinatorial characterization of longest tours, which yields an $O(n\log n)$ time algorithm for computing them.

Let S be a set of n points in the unit square [0, 1]2, one of which is the origin. We construct n pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in S, and the rectangles jointly cover at least a positive constant area (about 0.09). This is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2.

We obtain new lower and upper bounds for the maximum multiplicity of some weighted, and respectively non-weighted, common geometric graphs drawn on $n$ points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of $n$ points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits Omega (8.65^n) different triangulations. This improves the bound Omega (8.48^n) achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al. (ii) We present a new lower bound of Omega(11.97^n) for the number of non-crossing spanning trees of the double chain composed of two convex chains. The previous bound, Omega(10.42^n), stood unchanged for more than 10 years. (iii) Using a recent upper bound of 30^n for the number of triangulations, due to Sharir and Sheffer, we show that n points in the plane in general position admit at most O(68.664^n) non-crossing spanning cycles. (iv) We derive exponential lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). It was known that the number of longest non-crossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we obtain tight bounds for the number of longest and shortest tours. We give a combinatorial characterization of the longest tours, which leads to an O(n log n) time algorithm for computing them.

A length preserving transformation of a polygon is any transformation of its vertices that preserves the lengths of the edges. In the video segment we will demonstrate three types of length preserving transformations: pocket flips, flipturns, and pops. We present sequences of such operations and study their power (or weakness) in the attempt of convexifying simple polygons.

Let Ω be a disk of radius R in the plane. A set F of closed unit disks contained in Ω forms a maximal packing if the unit disks are pairwise disjoint and the set is maximal: i.e., it is not possible to add another disk to F while maintaining the packing property. A point p is hidden within the “forest” defined by F if any ray with apex p intersects some disk of F: that is, a person standing at p can hide without being seen from outside the forest. We show that if the radius R of Ω is large enough, one can find a hidden point for any maximal packing of unit disks in Ω. This proves a conjecture of Joseph Mitchell. We also present an O(n5/2 log n)-time algorithm that, given a forest with n (not necessarily congruent) disks, computes the boundary illumination map of all disks in the forest.

We present two new approximation algorithms with (improved) constant ratios for selecting $n$ points in $n$ unit disks such that the minimum pairwise distance among the points is maximized. (I) A very simple $O(n \log{n})$-time algorithm with ratio $0.5110$ for disjoint unit disks. In combination with an algorithm of Cabello~\cite{Ca07}, it yields a $O(n^2)$-time algorithm with ratio of $0.4487$ for dispersion in $n$ not necessarily disjoint unit disks. (II) A more sophisticated LP-based algorithm with ratio $0.6495$ for disjoint unit disks that uses a linear number of variables and constraints, and runs in polynomial time. The algorithm introduces a novel technique which combines linear programming and projections for approximating distances. The previous best approximation ratio for disjoint unit disks was $\frac{1}{2}$. Our results give a partial answer to an open question raised by Cabello~\cite{Ca07}, who asked whether $\frac{1}{2}$ could be improved.

We revisit several maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, 1993). Given a set of $n$ points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching (b) a Hamiltonian path (c) a spanning tree. Here we obtain new results for (b) and (c), as well as for the Hamiltonian cycle problem: (i) For the longest non-crossing Hamiltonian path problem, we give an approximation algorithm with ratio $\frac{2}{\pi+1} \approx 0.4829$. The previous best ratio, due to Alon et al., was $1/\pi \approx 0.3183$. Moreover, the ratio of our algorithm is close to $2/\pi$ on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time. (ii) For the longest non-crossing spanning tree problem, we give an approximation algorithm with ratio $0.502$ which runs in $O(n \log{n})$ time. The previous ratio, $1/2$, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first re-derive the result of Alon et al. with a faster $O(n \log{n})$-time algorithm and a very simple analysis. (iii) For the longest non-crossing Hamiltonian cycle problem, we give an approximation algorithm whose ratio is close to $2/\pi$ on a relatively broad class of instances: for point sets with the product $\bf{\langle}$~diameter~$\times$ ~convex hull size $\bf{\rangle}$ much smaller than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time. No previous approximation results were known for this problem.

We revisit the problem of pursuit-evasion in a grid introduced by Sugihara and Suzuki [SIAM J. Discrete Math., 2 (1989), pp. 126–143] in the line-of-sight vision model. Consider an arbitrary evader Z with the maximum speed of 1 who moves (in a continuous way) on the streets and avenues of an $n\times n$ grid $G_n$. The cunning evader is to be captured by a group of pursuers, possibly only one. The maximum speed of the pursuers is $s\geq1$; s is a constant for each pursuit-evasion problem considered, but several values for s are studied. We prove several new results (no such algorithms were available for capture using one, two, or three pursuers having a constant maximum speed limit): (i) A randomized algorithm through which one pursuer A with a maximum speed of $s\geq3$ can capture an arbitrary evader Z in $G_n$ in expected polynomial time. For instance, the expected capture time is $O(n^{1+\log_{6/5}16})=O(n^{16.21})$ for $s=3$, $O(n^{1+\log12})=O(n^{4.59})$ for $s=4$, $O(n^{1+\log60/13})=O(n^{3.21})$ for $s=6$, and it approaches $O(n^3)$ with the further increase of s. (ii) A randomized algorithm for capturing an arbitrary evader in $O(n^3)$ expected time using two pursuers who can move slightly faster than the evader ($s=1+\varepsilon$ for any $\varepsilon>0$). (iii) Randomized algorithms for capturing a certain “passive” evader using either a single pursuer who can move slightly faster than the evader ($s=1+\varepsilon$ for any $\varepsilon>0$) or two pursuers having the same maximum speed as the evader ($s=1$). (iv) A deterministic algorithm for capturing an arbitrary evader in $O(n^2)$ time, using three pursuers having the same maximum speed as the evader ($s=1$).

A Steiner star for a set P of n points in ℝd connects an arbitrary center point to all points of P, while a star connects a point p ∊ P to the remaining n − 1 points of P. All connections are realized by straight line segments. Fekete and Meijer showed that the minimum star is at most √2 times longer than the minimum Steiner star for any finite point configuration in ℝd. The maximum ratio between them, over all finite point configurations in ℝd, is called the star Steiner ratio in ℝd. It is conjectured that this ratio is 4/π = 1.2732… in the plane and 4/3 = 1.3333… in three dimensions. Here we give upper bounds of 1.3631 in the plane, and 1.3833 in 3-space, thereby substantially improving recent upper bounds of 1.3999, and √2 — 10−-4, respectively. Our results also imply improved bounds on the maximum ratios between the minimum star and the maximum matching in two and three dimensions. Our method exploits the connection with the classical problem of estimating the maximum sum of pairwise distances among n points on the unit sphere, first studied by László Fejes Tóth. It is quite general and yields the first non-trivial estimates below √2 on the star Steiner ratios in arbitrary dimensions. We show, however, that the star Steiner ratio in ℝd tends to √2, the upper bound given by Fekete and Meijer, as d goes to infinity. Our estimates on the star Steiner ratios are therefore much closer to the conjectured values in higher dimensions! As it turns out, our estimates as well as the conjectured values of the Steiner ratios (in the limit, for n going to infinity) are related to the classical infinite Wallis product: .

The study of extremal problems on triangle areas was initiated in a series of papers by Erdös and Purdy in the early 1970s. Here we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles.

Let G be a connected graph, and let V and $V'$ be two n-element subsets of its vertex set $V(G)$. Imagine that we place a chip at each element of V and we want to move them into the positions of $V'$ (V and $V'$ may have common elements). A move is defined as shifting a chip from $v_1$ to $v_2$ ($v_1,v_2 \in V(G)$) on a path formed by edges of G so that no intermediate vertices are occupied. We give upper and lower bounds on the number of moves that are necessary and analyze the computational complexity of this problem under various assumptions: labeled versus unlabeled chips, arbitrary graphs versus the case when the graph is the rectangular (infinite) planar grid, etc. We prove hardness and inapproximability results for several variants of the problem. We also give a linear time algorithm which performs an optimal (minimum) number of moves for the unlabeled version in a tree, and a constant-ratio approximation algorithm for the unlabeled version in a graph. The graph algorithm uses the tree algorithm as a subroutine.

Given a finite set of points S in Rd, consider visiting thepoints in S with a polygonal path that makes a minimum number ofturns, or equivalently, has the the minimum number of segments(links). We call this minimization problem the minimum linkspanning path problem. This natural problem has appeared severaltimes in the literature under different variants. The simplest oneis where the allowed paths are axis-aligned. Let L(S) be theminimum number of links of an axis-aligned path for S denote by Gdn the d-dimensional grid of size n. Kranakis, Krizanc andMeertens (Ars Combinatoria, vol. 38, pp. 177--192, 1994)showed that in 2-dimensions L(G2n)=2n-1 and in three dimensions 4/3 n2-O(n)< L(G3n) < 3/2 n2+O(n). Kranakiset al. conjectured that, for all d ≥ 3, L(Gdn)= d/d-1 nd-1 ± O(nd-2). We prove theconjecture for d=3 by showing that L(G3n) ≥ 3/2 n2 -O(n). For d=4, we prove that 4/3 n3 -O(n2) ≤ L(G4n) ≤ 4/3 n3 +O(n5/2).For general d, we give new estimates on L(Gdn), that bring usvery close to the conjectured value. The new lower bound of (1+ 1/d)nd-1-O(nd-2) improves previous result byCollins and Moret (Information Processing Letters, vol. 68,pp. 317--319, 1998), while the new upper bound of (1+ 1/d-1)nd-1+O(nd-3/2) differs from the conjecturedvalue only in the lower order terms. For arbitrary point sets, we give an exact bound on the minimumnumber of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in anynumber of dimensions d. For the general problem of traversing anarbitrary set of points in Rd with an axis-aligned spanning pathhaving a minimum number of links, we present a constant ratio(depending on the dimension d) approximation algorithm.

Consider the following survival problem:Given a set of k trajectories (paths) with maximum unit speed in a boundedregion over a (long) time interval [0,T], find another trajectory (if itexists) subject to the same maximum unit speed limit, that avoids (that is, stays at a safe distance of)each of the other trajectories over the entire time interval. We call this variant the continuous model of the survival problem. The discrete model of this problem is: Given the trajectories (paths) of k point robots in a graph over a (long)time interval 0,1,2,...,T, find a trajectory (path) for anotherrobot, that avoids each of the other k at any time instance in thegiven time interval. We introduce the notions of survival number of a region,and that of a graph, respectively, as the maximum number oftrajectories which can be avoided in the region (resp. graph). We give the first estimates on the survival number of the n x n grid Gn, and also devise an efficient algorithm for the corresponding safepath planning problem in arbitrary graphs. We then show that our estimates on the survival number of Gn%on the number of paths that can be avoided in Gn can be extended for the survival number of a bounded (square) region.In the final part of our paper, we consider other related offlinequestions, such as the maximum number of men problem and the spy problem.

Abstract Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in theplane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk is lifted from the plane and placed back in the plane atanother location, without intersecting any other disk. We discuss efficient algorithms for this task and estimate their number of moves under different assumptions on disk radii. We then extend our results forarbitrary disks to systems of pseudodisks, in particular to sets of homothetic copies of a convex object. 1 Introduction Consider a set (system) of n pairwise disjoint objects in the plane that need to be brought from a givenstart (initial) configuration S into a desired goal (target) configuration T. The motion planning problemfor such a system is that of computing a sequence of object motions (schedule) that achieves this task. If

Given a set P of n points in convex position in the plane, we prove that there exists a point p ∈ P such that the number of distinct distances from p is at least [(13n-6)/36]. The best previous bound, [n/3], from 1952, is due to Leo Moser.

We study dynamic self-reconfiguration of modular metamorphicsystems. We guarantee the feasibility of motion planning in a rectangular model consisting of square modules that are allowed to slide along or rotate about one another. That is, we show that any two connected configurations of the same numberof modules can be transformed into each other by a sequence ofmoves so that all intermediate configurations are connected. This settles a conjecture formulated in [6].

In this paper, we address a number of issues related to motion planning and analysis of rectangular metamorphic robotic systems. We first present a distributed algorithm for reconfiguration that applies to a relatively large subclass of configurations, called horizontally convex configurations. We then discuss several fundamental questions in the analysis of metamorphic systems. In particular, the following two questions are shown to be decidable: 1) whether a given set of motion rules maintains connectivity; 2) whether a goal configuration is reachable from a given initial configuration (at specified locations). In the general case in which each module has an internal state, the following is shown to be undecidable: given a set of motion rules, whether there exists a certain type of configuration called a uniform straight-chain configuration that yields a disconnected configuration.

We examine the problem of dynamic self-reconfiguration of a modular robotic system (frequently referred to as self-reconfigurable or metamorphic system), to a formation aimed at reaching a specified target position with one of the modules as quickly as possible. We present a number of high speed formations for both rectangular and hexagonal systems, and prove upper and lower bounds on the speed of locomotion. In particular, the formations presented achieve constant ratio guarantee on the time to reach a given target in the asymptotic sense.

We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the efficient construction of binary space partitions (BSP's) of axis-parallel segments, rectangles, and hyperrectangles. (a) A consequence of the analysis in \cite{dAF} is that any set of $n$ axis-parallel and pairwise-disjoint line segments in the plane admits a binary space partition of size at most $2n-1$. We establish a worst-case lower bound of $2n-o(n)$ for the size of such a BSP, thus showing that this bound is almost tight in the worst case. (b) We give an improved worst-case lower bound of $\frac{9}{4}n-o(n)$ on the size of a BSP for isothetic pairwise disjoint rectangles. (c) We present simple methods, with equally simple analysis, for constructing BSP's for axis-parallel segments in higher dimensions, simplifying the technique of \cite{PY2} and improving the constants. (d) We obtain an alternative construction (to that in \cite{PY2}) of BSP's for collections of axis-parallel rectangles in 3-space. (e) We present a construction of BSP's of size $O(n^{5/3})$ for $n$ axis-parallel pairwise disjoint 2-rectangles in $\reals^4$, and give a matching worst-case lower bound of $\Omega(n^{5/3})$ for the size of such a BSP. (f) We extend the results of \cite{PY2} to axis-parallel $k$-dimensional rectangles in $\reals^d$, for $k