The Medusa of Spatial Sorting: 3D Kinetic Alpha Complexes and Implementation

Michael Kerber, Herbert EdelsbrunnerarXiv 2012 · arXiv

Abstract

This paper introduces a robust algorithmic framework for constructing the "Medusa," a 4D space-time cell complex that tracks the topological evolution of moving particles. By extending kinetic data structures from Delaunay triangulations to fixed-radius alpha complexes and applying rigorous exact geometric computation, the authors provide a tool to objectively measure complex biological processes like cell segregation.

Introduction

In developmental biology, researchers often observe "spatial sorting"—for example, when two different types of cells intermix and then spontaneously segregate into a core-and-shell structure. While visually striking, these processes are difficult to quantify objectively.

To solve this, the authors previously proposed the "Medusa," a mathematical representation created by stacking 3D geometric regions (restricted Voronoi cells) over time to form a 4D object. However, building this structure computationally is a significant challenge. As points move, the underlying geometry (the Delaunay triangulation) changes discretely, and the "alpha complex" (a subset of the triangulation representing the shape) changes even more frequently. Maintaining "exactness"—ensuring the computer doesn't crash or produce nonsense due to rounding errors—is the core challenge addressed here.

The Medusa Framework

The Medusa is a 4D cell complex that captures the continuous and discrete changes of a set of moving points. Conceptually, it can be thought of as the "trace" of a 3D shape as it evolves through time.

Conceptual representation of the Medusa as a space-time cell complex tracking moving simplices.

The authors prove that a combinatorial version of the Medusa, built from simplices rather than Voronoi cells, is topologically equivalent to the more complex Voronoi version, making it much easier to compute. To ensure the Medusa remains a valid 4D cell complex, "degenerate" cells are introduced at the exact moments of topological flips or point insertions, acting as the connective tissue across time.

Algorithmic Implementation

The authors build upon the Kinetic Data Structures (KDS) framework. A KDS maintains a geometric structure by calculating "certificates"—mathematical conditions that remain true as long as the structure doesn't change. When a certificate's value hits zero, an "event" occurs, and the structure is updated.

Key methodological contributions include:

  • Kinetic Alpha Complexes: Moving beyond standard kinetic Delaunay triangulations, the authors track "radius events"—the exact moments when the circumradius of a triangle or tetrahedron crosses a fixed threshold.
  • Exact Geometric Computation (EGC): They use the CGAL library to handle algebraic numbers exactly. This prevents the "cascading failures" common in geometric software when floating-point approximations lead to logically inconsistent states.

A major insight is the G-criticality Lemma, which proves that flip events and radius events are sufficient to maintain the alpha complex, significantly reducing the number of certificates to track.

Experimental Validation

The algorithm was evaluated using synthetic datasets generated by COMPUCELL3D, a software suite for simulating biological cell segregation. The datasets involve 10 to 160 cell trajectories where cells move in piecewise linear paths.

Simulation of cell segregation where blue cells engulf red cells, forming a core-and-shell structure.

The simulation specifically models blue cells engulfing red cells, providing a controlled environment to test how well the Medusa captures topological shifts.

Performance and Optimizations

The paper focuses heavily on optimization to bridge the performance gap between theory and practice. Maintaining the alpha complex is computationally expensive because radius events involve high-degree polynomials (up to degree 10).

Through a combination of algebraic filtering and caching, the authors implemented several key optimizations:

  • Certificate Reduction: By removing radius certificates for simplices that are already "short," they reduced the number of certificates and running time by roughly 50%.
  • Degree Reduction: By deriving a more efficient formula for triangle circumradii, they lowered the polynomial degree from 10 to 6, resulting in another 2x speedup.

The final optimized version is roughly 15 times faster than the naive implementation. Interestingly, once the kinetic alpha complex is maintained, the actual construction of the 4D Medusa adds negligible computational cost.

Conclusion

The Medusa framework provides a rigorous way to quantify spatial sorting. While the current implementation assumes distinct events and fixed-radius balls, future work will focus on handling simultaneous events (degeneracies), generalizing to non-spherical cell shapes, and scaling to thousands of trajectories.

Summary updated

Abstract

Motivated by an application in cell biology, we consider spatial sorting processes defined by particles moving from an initial to a final configuration. We describe an algorithm for constructing a cell complex in space-time, called the medusa, that measures topological properties of the sorting process. The algorithm requires an extension of the kinetic data structures framework from Delaunay triangulations to fixed-radius alpha complexes. We report on several techniques to accelerate the computation.
BibTeX
@misc{kerber2012medusa,
  author = {Michael Kerber and Herbert Edelsbrunner},
  title = {{The Medusa of Spatial Sorting: 3D Kinetic Alpha Complexes and Implementation}},
  year = {2012},
  eprint = {1209.5434},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1209.5434},
}
Figure