A Note on Binary Plane Partitions

Abstract. This paper considers binary space partition s (BSP for short) for disjoint line segments in the plane. The BSP for a disjoint set of objects is a scheme dividing the space recursively by hyperplanes until the resulting fragments of objects are separated. The size of a BSP is the number of resulting fragments of the objects. We show that the minimal size of a BSP for n disjoint line segments in the plane is Ω (n log n /log log n) in the worst case.     

Binary Plane Partitions for Disjoint Line Segments

A binary space partition (BSP) for a set of disjoint objects in Euclidean space is a recursive decomposition where each step partitions the space (and possibly some of the objects) along a hyperplane and recurses on the objects clipped in each of the two open half-spaces. The size of a BSP is defined as the number of resulting fragments of the input objects. It is shown that every set of n disjoint line segments in the plane admits a BSP of size O(nlog n/log log n). This bound is the best possible.     

Every Set of Disjoint Line Segments Admits a Binary Tree

Given a set of n disjoint line segments in the plane, we show that it is always possible to form a tree with the endpoints of the segments such that each line segment is an edge of the tree, the tree has no crossing edges, and the maximum vertex degree of the tree is 3. Furthermore, there exist configurations of line segments where any such tree requires degree 3. We provide an O(nlog n) time algorithm for constructing such a tree, and show that this is optimal. Received September 14, 1999, and in revised form January 17, 2001. Online publication August 29, 2001.     

Segment Intersection Searching Problems in General Settings

   Abstract. We consider segment intersection searching amidst (possibly intersecting) algebraic arcs in the plane. We show how to preprocess n arcs in time O(n ^2+ɛ ) into a data structure of size O(n ^2+ɛ ) , for any ɛ >0 , such that the k arcs intersecting a query segment can be counted in time O( log n) or reported in time O( log n+k) . This problem was extensively studied in restricted settings (e.g., amidst segments, circles, or circular arcs), but no solution with comparable performance was previously presented for the general case of possibly intersecting algebraic arcs. Our data structure for the general case matches or improves (sometimes by an order of magnitude) the size of the best previously presented solutions for the special cases. As an immediate application of this result, we obtain an efficient data structure for the triangular windowing problem, which is a generalization of triangular range searching. As another application, the first substantially subquadratic algorithm for a red—blue intersection counting problem is derived. We also describe simple data structures for segment intersection searching among disjoint arcs, and for ray shooting among possibly intersecting arcs.     

Pointed binary encompassing trees: Simple and optimal

For n disjoint line segments in the plane we construct in optimal O(nlogn) time and linear space an encompassing tree of maximum degree three such that at every vertex v all edges of the tree that are incident to v lie in a halfplane bounded by the line through the input segment which v is an endpoint of. In particular, this tree is pointed since every vertex has an incident angle greater than π. Such a pointed binary tree can be augmented to a minimum pseudo-triangulation. It follows that every set of disjoint line segments in the plane has a constrained minimum pseudo-triangulation whose maximum vertex degree is bounded by a constant.     

Segment Intersection Searching Problems in General Settings

Abstract. We consider segment intersection searching amidst (possibly intersecting) algebraic arcs in the plane. We show how to preprocess n arcs in time O(n ^2+ɛ ) into a data structure of size O(n ^2+ɛ ) , for any ɛ >0 , such that the k arcs intersecting a query segment can be counted in time O( log n) or reported in time O( log n+k) . This problem was extensively studied in restricted settings (e.g., amidst segments, circles, or circular arcs), but no solution with comparable performance was previously presented for the general case of possibly intersecting algebraic arcs. Our data structure for the general case matches or improves (sometimes by an order of magnitude) the size of the best previously presented solutions for the special cases. As an immediate application of this result, we obtain an efficient data structure for the triangular windowing problem, which is a generalization of triangular range searching. As another application, the first substantially subquadratic algorithm for a red—blue intersection counting problem is derived. We also describe simple data structures for segment intersection searching among disjoint arcs, and for ray shooting among possibly intersecting arcs.     

Disjoint Compatible Geometric Matchings

We prove that for every set of n pairwise disjoint line segments in the plane in general position, where n is even, there is another set of n segments such that the 2n segments form pairwise disjoint simple polygons in the plane. This settles in the affirmative the Disjoint Compatible Matching Conjecture by Aichholzer et al. (Comput. Geom. 42:617–626, 2009). The key tool in our proof is a novel subdivision of the free space around n disjoint line segments into at most n+1 convex cells such that the dual graph of the subdivision contains two edge-disjoint spanning trees.     

A Ramsey-Type Result for Convex Sets

Given a family of n convex compact sets in the plane, one canalways choose n of them which are either pairwise disjoint orpairwise intersecting. On the other hand, there exists a familyof n segments in the plane such that the maximum size of a subfamilywith pairwise disjoint or pairwise intersecting elements inn^log2/log5 n^0·431.     

Dynamic Point Location in General Subdivisions

The dynamic planar point location problem is the task of maintaining a dynamic set S of n nonintersecting (except possibly at endpoints) line segments in the plane under the following operations:

• Locate (: point): Report the segment immediately above , i.e., the first segment intersected by an upward vertical ray starting at ;

• Insert (: segment): Add segment to the collection of segments;

• Delete (: segment): Remove segment from the collection of segments.

We present a solution which requires space O(n) and has query and insertion time O(log n log log n) and deletion time O(log²n). The bounds for insertions and deletions are amortized. A query time below O(log²n) was previously only known for monotone subdivisions and subdivisions consisting of horizontal segments and required nonlinear space.     

A Constant Bound for Geometric Permutations of Disjoint Unit Balls

   Abstract. We prove that a set of n disjoint unit balls in R ^d admits at most four distinct geometric permutations, or line transversals, thus settling a long-standing conjecture in combinatorial geometry. The constant bound significantly improves upon the Θ (n ^d-1 ) bound for disjoint balls of unrestricted radii.     

Disjoint edges in geometric graphs

Answering an old question in combinatorial geometry, we show that any configuration consisting of a setV ofn points in general position in the plane and a set of 6n – 5 closed straight line segments whose endpoints lie inV, contains three pairwise disjoint line segments.Research supported in part by an Allon Fellowship and by a Bat Sheva de-Rothschild grant.     

Tight Bounds for Connecting Sites Across Barriers

Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight line minimum cost spanning tree on the sites, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines, it is known that there is a spanning tree such that every barrier is crossed by tree edges, and this bound is asymptotically optimal. Asano et al. showed that if the barriers are pairwise disjoint line segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Lower bound constructions are known with 3 crossings per barrier and 2n total cost. We obtain tight bounds on the minimum cost of spanning trees in the special case where the barriers are interior disjoint line segments that form a convex subdivision of the plane and there is a point in every cell of the subdivision. In particular, we show that there is a spanning tree such that every barrier crosses at most 2 tree edges, and there is a spanning tree of total cost 5n/3. Both bounds are the best possible. Work by Eynat Rafalin and Diane Souvaine was supported by the National Science Foundation under Grant #CCF-0431027. E. Rafalin’s research conducted while at Tufts University.     

Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles

We provide a variety of new upper and lower bounds and simpler proof techniques for the efficient construction of binary space partitions (BSPs) of axis-parallel rectangles of various dimensions. (a) We construct a set of $n$ disjoint axis-parallel segments in the plane such that any binary space auto-partition has size at least $2n-o(n)$, almost matching an upper bound of dAmore and Franciosa. (b) We establish a similar lower bound of $7n/3-o(n)$ for disjoint rectangles in the plane. (c) We simplify and improve BSP constructions of Paterson and Yao for disjoint segments in $\reals^d$ and disjoint rectangles in $\reals^3$. (d) We derive a worst-case bound of $\Theta(n^{5/3})$ for the size of BSPs of disjoint $2$-rectangles in $4$-space. (e) For disjoint $k$-rectangles in $d$-space, we prove the worst-case bound $\Theta(n^{d/(d-k)})$, for any $k<d/2$; this bound holds for all $k<d$ if the rectangles are allowed to intersect.     

A Helly-Type Theorem for Line Transversals to Disjoint Unit Balls

   Abstract. Let F be a family of disjoint unit balls in R ³ . We prove that there is a Helly-number n ₀ ≤ 46 , such that if every n ₀ members of F ( | F | ≥ n ₀ ) have a line transversal, then F has a line transversal. In order to prove this we prove that if the members of F can be ordered in a way such that every 12 members of F are met by a line consistent with the ordering, then F has a line transversal. The proof also uses the recent result on geometric permutations for disjoint unit balls by Katchalski, Suri, and Zhou.     

Almost Disjoint Triangles in 3-Space

   Abstract. Two triangles are called almost disjoint if they are either disjoint or their intersection consists of one common vertex. Let f(n) denote the maximum number of pairwise almost disjoint triangles that can be found on some vertex set of n points in 3-space. Here we prove that f(n)=Ω(n ^3/2 ) .     

Enclosing a Set of Objects by Two Minimum Area Rectangles

In this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose anO(nα(n)log n) worst-case time algorithm, where α( ) is the inverse Ackermann's function, for finding, given a setMof points, segments and polygons defined bynvertices, a pair of axis-parallel rectangles (s, t) such thats∪tencloses all objects inMand area(s)+area(t) is minimum. The algorithm works inO(nα(n) log log n) worst-case space. Moreover, we prove an Ω(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case timeO(n log n), using worst-case spaceO(n log log n).     

Cuttings for Disks and Axis-Aligned Rectangles in Three-Space

We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r∈?, a $\frac{1}{r}We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r∈ℕ, a \frac1r\frac{1}{r} -cutting is a covering of the space with simplices such that the interior of each simplex intersects at most n/r objects. For n pairwise disjoint disks in ℝ³ and a parameter r∈ℕ, we construct a \frac1r\frac{1}{r} -cutting of size O(r ²). For n axis-aligned rectangles in ℝ³, we construct a \frac1r\frac{1}{r} -cutting of size O(r ^3/2). As an application related to multi-point location in three-space, we present tight bounds on the cost of spanning trees across barriers. Given n points and a finite set of disjoint disk barriers in ℝ³, the points can be connected with a straight line spanning tree such that every disk is stabbed by at most O(?n)O(\sqrt{n}) edges of the tree. If the barriers are axis-aligned rectangles, then there is a straight line spanning tree such that every rectangle is stabbed by O(n ^1/3) edges. Both bounds are best possible.     

On Order Types of Systems of Segments in the Plane

Let r(n) denote the largest integer such that every family C\mathcal{C} of n pairwise disjoint segments in the plane in general position has r(n) members whose order type can be represented by points. Pach and Tóth gave a construction that shows r(n) < n ^log8/log9 (Pach and Tóth 2009). They also stated that one can apply the Erdős–Szekeres theorem for convex sets in Pach and Tóth (Discrete Comput Geom 19:437–445, 1998) to obtain r(n) > log₁₆ n. In this note, we will show that r(n) > cn ^1/4 for some absolute constant c.     

New Similarity Measures between Polylines with Applications to Morphing and Polygon Sweeping

   Abstract. We introduce two new related metrics, the geodesic width and the link width , for measuring the ``distance' between two nonintersecting polylines in the plane. If the two polylines have n vertices in total, we present algorithms to compute the geodesic width of the two polylines in O(n <sup>2</sup> log n) time using O(n <sup>2</sup> ) space and the link width in O(n <sup>3</sup> log n) time using O(n <sup>2</sup> ) working space where n is the total number of edges of the polylines. Our computation of these metrics relies on two closely related combinatorial strutures: the shortest-path diagram and the link diagram of a simple polygon. The shortest-path (resp., link) diagram encodes the Euclidean (resp., link) shortest path distance between all pairs of points on the boundary of the polygon. We use these algorithms to solve two problems: • Compute a continuous transformation that ``morphs' one polyline into another polyline. Our morphing strategies ensure that each point on a polyline moves as little as necessary during the morphing, that every intermediate polyline is also simple and disjoint to any other intermediate polyline, and that no portion of the polylines to be morphed is stretched or compressed by more than a user-defined parameter during the entire morphing. We present an algorithm that computes the geodesic width of the two polylines and utilizes it to construct a corresponding morphing strategy in O(n ² log ² n) time using O(n ² ) space. We also give an O(nlog n) time algorithm to compute a 2-approximation of the geodesic width and a corresponding morphing scheme. • Locate a continuously moving target using a group of guards moving inside a simple polygon. The guards always determine a simple polygonal chain within the polygon, with consecutive guards along the chain being mutually visible. We compute a strategy that sweeps such a chain of guards through the polygon in order to locate a target. We compute in O(n ³ ) time and O(n ² ) working space the minimum number r ^* of guards needed to sweep an n -vertex polygon. We also give an approximation algorithm, using O(n log n) time and O(n) space, to compute an integer r such that max(r - 16, 2)≤ r ^* ≤ r and P can be swept with a chain of r guards.     

Alternating Paths along Axis-Parallel Segments

It is shown that for a set S of n pairwise disjoint axis-parallel line segments in the plane there is a simple alternating path of length . This bound is best possible in the worst case. In the special case that the n pairwise disjoint axis-parallel line segments are protruded (that is, if the intersection point of the lines through every two nonparallel segments is not visible from both segments), there is a simple alternating path of length n. Work on this paper was partially supported by National Science Foundation grants CCR-0049093 and IIS-0121562. A preliminary version of this paper has appeared in the Proceedings of the 8th International Workshop on Algorithms and Data Structures (Ottawa, ON, 2003), vol. 2748 of Lecture Notes on Computer Science, Springer, Berlin, 2003, pp. 389–400.