Spanning Trees Crossing Few Barriers

Tetsuo Asano, Mark de Berg, Otfried Cheong, Leonidas J. Guibas, Jack Snoeyink, Hisao TamakiDiscret. Comput. Geom 2003 · DOI

Introduction

In computational geometry, a fundamental challenge involves connecting a set of $n$ points in a plane while minimizing interactions with a set of $m$ geometric "barriers." This paper investigates the existence of spanning trees that cross these barriers as few times as possible. The authors demonstrate that for disjoint convex barriers, a spanning tree with a total crossing cost of $O(n + m)$ is always achievable. This theoretical result has significant practical implications, particularly in accelerating "batched" point location within complex geometric subdivisions.

Problem Definition and Motivation

The primary motivation for this work is the point location problem: determining which region of a planar subdivision contains a given point. While standard algorithms solve this in $O(\log m)$ time per point, a batch of $n$ points typically requires $O(n \log m)$ total time.

A basic configuration of $n$ points and $m$ parallel segments, illustrating how barriers can force crossings.

However, if the points are connected by a spanning tree with a low crossing number, one can locate the first point and then "walk" along the tree edges to locate the others. If the total number of boundary crossings is linear, the entire batch can be processed in $O(n + m)$ time. The core question is: what is the minimum number of crossings guaranteed for any arbitrary set of points and barriers?

Constructive Methods

The authors employ two primary techniques to establish their upper bounds:

  1. Binary Space Partitions (BSPs): For "uncluttered" scenes where objects are not packed with extreme density, the authors utilize orthogonal BSPs. By recursively dividing the plane into horizontal and vertical regions, they associate points with specific partitions. The spanning tree is then constructed by connecting points across these splitting lines, with the total cost bounded by the number of fragments created by the BSP.
  2. The Spined Tree Construction: For the more complex case of disjoint convex barriers, the authors introduce the "spined tree." This construction involves an incremental approach where points are inserted based on their y-coordinates. The tree is updated to ensure that no single barrier is crossed excessively, using a sophisticated inductive proof involving Davenport–Schinzel sequences to bound total intersections.
Illustration of a spanning tree edge crossing barriers within a partitioned region, a key component of the recursive construction.

Key Results and Insights

The paper establishes several worst-case optimal bounds for the total crossing cost:

  • Intersecting Line Segments: $O(\min(m^2, m\sqrt{n}))$.
  • Disjoint Line Segments: $O(m)$. The authors prove a tree exists where no single segment is crossed more than four times.
  • $\kappa$-cluttered Scenes (e.g., Discs): $O(n + m)$.
  • Disjoint Convex Objects: $O(n + m)$, specifically bounded by $4m + 3n$.

These results highlight that the "clutteredness" and disjointness of objects are the primary factors in crossing complexity. Forcing barriers to be disjoint is the critical requirement for achieving linear or near-linear crossing costs. Furthermore, the authors provide lower-bound examples, such as grid-like barrier arrangements, to demonstrate that their results are asymptotically optimal.

Conclusion and Future Work

While the paper provides robust theoretical guarantees, several avenues for future research remain. The algorithm for the general convex case is currently less efficient than the BSP-based approach; developing an $O((n + m) \log m)$ algorithm for arbitrary disjoint segments is an open challenge. Additionally, the constants in the current bounds (such as the four crossings per segment) may not be tight. Future work could also extend these concepts beyond spanning trees to other structures like Hamiltonian paths or matchings with low crossing numbers.

Summary updated

BibTeX
@article{asano2003spanning,
  author = {Tetsuo Asano and Mark de Berg and Otfried Cheong and Leonidas J. Guibas and Jack Snoeyink and Hisao Tamaki},
  title = {{Spanning Trees Crossing Few Barriers}},
  journal = {Discret. Comput. Geom.},
  year = {2003},
  doi = {10.1007/s00454-003-2853-5},
}
Figure