A fast algorithm for computing a planar support for non-piercing rectangles

Ambar Pal, Rajiv Raman, Saurabh Ray, Karamjeet Singh

Abstract

This paper introduces a near-linear time algorithm for constructing a planar support for hypergraphs where hyperedges are defined by points contained within non-piercing axis-aligned rectangles. By employing a greedy sweep-line approach combined with advanced data structures, the authors achieve a running time of $O(n \log^2 n + (n+m) \log m)$. This represents a significant improvement over prior polynomial-time methods. The algorithm naturally produces straight-line embeddings, enhancing visualization and enabling new approximation bounds for geometric Hitting Set problems.

Introduction

Hypergraphs serve as a fundamental model for representing multi-way relationships in fields ranging from VLSI design to social network analysis. A support for a hypergraph is a graph on the same vertex set such that for every hyperedge, the induced subgraph is connected. A planar support is particularly desirable for visualization as it can be embedded in the plane without edge crossings. However, determining the existence of a planar support is NP-hard for general hypergraphs.

This work focuses on geometric hypergraphs where vertices are points in $\mathbb{R}^2$ and hyperedges are defined by axis-aligned rectangles. Specifically, it addresses non-piercing rectangles—a family where any two intersecting rectangles must have one containing at least one corner of the other. While planar supports were known to exist for such families, previous construction algorithms were computationally expensive, often exceeding cubic complexity.

Methodology: The Sweep-Line Approach

The core of the proposed solution is a sweep-line algorithm. As a vertical line moves from left to right across the plane, the algorithm incrementally builds the support graph.

Valid Delaunay Edges

When the sweep-line encounters a point, the algorithm attempts to connect it to previously processed points to its left. It prioritizes "valid Delaunay edges"—edges where the bounding box of the two points contains no other points and does not "pierce" existing rectangles, thereby preserving the connectivity requirements of the hyperedges.

Data Structure Integration

To maintain efficiency, the algorithm integrates several sophisticated data structures:

  • Augmented Balanced Binary Search Trees: Used to identify "barriers" (rectangles that might obstruct an edge) in $O(\log m)$ time.
  • Brodal’s Dynamic Data Structure: Facilitates 2D range reporting to efficiently find potential neighbors.
  • 1D Range Search Trees: Manage "occlusions" to ensure new edges do not violate the planarity or connectivity of existing rectangles.

Geometric Invariants and Connectivity

The technical cornerstone of the algorithm is the proof that a greedy sweep-line maintains connectivity for every rectangle. This is achieved through a novel decomposition using "slabs," "strips," and "corridors."

Geometric decomposition of a rectangle into slabs and subslabs to maintain connectivity invariants during the sweep.

The algorithm ensures that points within specific slabs of a rectangle $R$ are connected to their rightmost neighbors, maintaining a "connectivity invariant" that propagates as the sweep-line progresses.

Decomposition of the plane into strips to manage point connectivity and edge validation.

Key Results

The primary contribution is the efficiency of the construction, reaching a complexity of $O(n \log^2 n + (n+m) \log m)$. This is a dramatic leap from the previous state-of-the-art of approximately $O(m^2(m^3 + n))$.

Furthermore, the algorithm's output—a straight-line planar embedding—is intrinsically better for visualization than the complex, multi-bend edges produced by earlier methods. The authors also demonstrate an application in approximation algorithms, providing a $(k + \epsilon)$-approximation for the Hitting Set problem for rectangle families with a piercing number of $k$.

Discussion and Future Work

While the algorithm is highly efficient for axis-aligned rectangles, extending it to arbitrary convex sets remains a challenge. The current implementation relies heavily on the axis-aligned nature of the shapes for its sweep-line and range-search optimizations. Future research may focus on reducing the $O(n \log^2 n)$ term to $O(n \log n)$ or exploring the "dual" problem, where rectangles act as vertices and points define the hyperedges.

Summary updated

BibTeX
@inproceedings{pal2024fast,
  author = {Ambar Pal and Rajiv Raman and Saurabh Ray and Karamjeet Singh},
  title = {{A fast algorithm for computing a planar support for non-piercing rectangles}},
  booktitle = {ISAAC},
  year = {2024},
  doi = {10.4230/lipics.isaac.2024.53},
}
Figure