Embedding the dual complex of hyper-rectangular partitions

Michael Kerber

TL;DR

Can you draw the dual simplicial complex of an axis-aligned box partition using straight lines such that every dual vertex sits inside its corresponding box without overlapping faces? This paper proves that deciding if such a valid embedding exists is NP-complete in 2D, and analyzes when the natural strategy—placing vertices at box centers—is mathematically guaranteed to work based on box aspect and size ratios ($\beta$-balancing).

What Problem Does This Paper Address?

When working with spatial data, image processing, or mesh generation, dividing a $d$-dimensional space into axis-aligned hyper-rectangles (boxes) is standard practice (e.g., quadtrees in 2D, octrees in 3D). To perform topological data analysis or piecewise linear interpolation, researchers often construct the dual complex—a simplicial complex where vertices represent boxes and higher-dimensional simplices represent intersections between boxes.

However, a critical geometric challenge arises: Can we realize this abstract dual complex as a valid geometric straight-line embedding in $\mathbb{R}^d$? Specifically, an embedding requires that:

  1. Faces are drawn as the convex hull of their boundary vertices.
  2. Simplices do not improperly intersect (no edges or faces crossing each other).
  3. Each dual vertex is faithfully placed inside the interior of its primary box.

This paper tackles two core questions:

  1. What is the computational complexity of determining whether such a faithful embedding exists?
  2. If we default to placing dual vertices strictly at the geometric centers of the boxes (the center projection), what balance conditions guarantee that this projection avoids overlapping, self-intersecting simplices?

Methods

The author approaches the problem via geometric topology and computational complexity:

  • The Embedding Theorem: Building on the nerve theorem and degree theory, the author proves that a projection is an embedding if and only if it preserves the orientation of every $d$-simplex (provided it preserves at least one). This reduces checking for global intersections to checking local simplex orientations.
  • Gadget-Based Reduction for Hardness: To prove NP-completeness of Faithful_Embed, the author reduces from grid3sat (a planar variant of 3-SAT laid out on an integer grid). The reduction constructs "thin rectangles" ($1 \times \ell$) arranged in "L-joints" and "L-cycles" to propagate Boolean truth values, terminating in clause gadgets that are embeddable if and only if the clause is satisfied.
  • Algebraic and Semi-Algebraic Verification: To analyze center projections:
  • In 2D, the condition that no orientation is inverted reduces to showing that no line can simultaneously intersect the candidate center regions of three mutually adjacent rectangles.
  • In 3D cubical partitions, proving orientation preservation involves checking that no plane intersects the bounding polytopes of box centers across all possible local intersection topologies. The author automated this proof using cylindrical algebraic decomposition (CAD) via qepcad.

Datasets

Not discussed in the paper. As a purely theoretical work in computational geometry, no empirical datasets were evaluated or introduced.

Key Insights and Ideas

  • Hardness in the Plane: Even in 2D with vertices constrained to a half-integral grid, deciding embeddability is NP-complete. Geometric constraints along chains of thin rectangles force rigid cascading choices, effectively acting as logical wires.
  • The Fragility of Aspect Ratios in High Dimensions:
  • In $\mathbb{R}^2$, controlling the ratio of the longest to shortest side across touching rectangles ($\beta$-balance) ensures center-embeddability as long as $\beta < 3$.
  • In $\mathbb{R}^d$ ($d \ge 3$), having rectangles with aspect ratio $1 + \epsilon$ is not enough; you can construct a counterexample for any $\beta > 1$ using non-cubical boxes.
  • Cubical Partitions Behave Better: If all boxes are forced to be cubes (aspect ratio 1), dimension 3 mirrors the planar case: cubical partitions are center-embeddable whenever $\beta < 3$.
  • The Dimensional Scaling Law: For cubical partitions in arbitrary dimension $d \ge 3$, counterexamples exist whenever the balance ratio exceeds $\frac{d}{d-2}$. Notice that as $d \to \infty$, the tolerable ratio approaches 1, meaning higher dimensions become increasingly intolerant of size disparities between neighboring cubes.

Key Results

  • NP-Completeness: The Faithful_Embed decision problem in $\mathbb{R}^2$ is NP-complete for half-integral projections, and NP-hard for arbitrary real projections.
  • Planar Balancing Bound: A planar partition is center-embeddable if it is $\beta$-balanced for $\beta < 3$. At $\beta = 3$, counterexamples exist where dual triangles degenerate into collinear line segments.
  • 3D Cubical Embedding: Cubical $\beta$-balanced partitions in $\mathbb{R}^3$ are guaranteed to be center-embeddable for $\beta < 3$.
  • Higher-Dimensional Bounds: For any dimension $d \ge 3$, there exists a $\beta$-balanced cubical partition that is not center-embeddable for any $\beta > \frac{d}{d-2}$.

Limitations and Future Work

  • Computer-Assisted Proofs: The proof for Theorem 9 (cubical partitions in $\mathbb{R}^3$) depends on automated quantifier elimination (qepcad). A direct, human-readable geometric argument is still desired.
  • The Gap in Higher Dimensions ($d \ge 4$): It remains an open conjecture whether cubical partitions with $\beta < \frac{d}{d-2}$ are always center-embeddable in dimensions $d \ge 4$. The double-exponential complexity of quantifier elimination currently prevents extending the computer-assisted proof.
  • Restricted Partitions: Future work includes exploring whether partitions produced by guillotine cuts (successive hyperplane splits) offer stronger embeddability guarantees, and whether algorithmic balancing strategies (analogous to quadtree balancing) can be made computationally efficient for general planar rectangular partitions.

Summary updated

Abstract

A rectangular partition is the partition of an (axis-aligned) rectangle into interior-disjoint rectangles. We ask whether a rectangular partition permits a nice drawing of its dual, that is, a straight-line embedding of it such that each dual vertex is placed into the rectangle that it represents. We show that deciding whether such a drawing exists is NP-complete. Moreover, we consider the drawing where a vertex is placed in the center of the representing rectangle and consider sufficient conditions for this drawing to be nice. This question is studied both in the plane and for the higher-dimensional generalization of rectangular partitions.
BibTeX
@article{kerber2013embedding,
  author = {Michael Kerber},
  title = {{Embedding the dual complex of hyper-rectangular partitions}},
  journal = {J. Comput. Geom.},
  year = {2013},
  url = {https://openreview.net/forum?id=2OrNyuVMei},
}
Figure