CS Paper Radar

Flip Graphs for Eight Points in Three Dimensions Are Connected

Marc Khoury

cs.CG ·submitted 2026-09-13 21:18 UTC · v1
theory

Abstract

We prove that every configuration of four through eight points in three-dimensional space, with no four points coplanar, has a connected full geometric flip graph under $2 \leftrightarrow 3$ flips. Every point remains fixed and present throughout the sequence. The proof brings each tetrahedralization into placing form at a convex hull vertex: the tetrahedra not incident to that vertex fill the convex hull of the remaining points. This reduction allows us to establish connectivity by induction, using the connectivity of regular tetrahedralizations. The main geometric tool is radial projection, which turns the tetrahedra incident to a hull vertex into a planar triangulation. When this planar triangulation is regular, varying its lifting heights produces legal spatial flips that progressively shrink the region occupied by the incident tetrahedra and reach placing form. Planar lifting criteria and compatibility constraints between the projections at different hull vertices resolve the remaining small cases. For eight points, at most 35 flips are needed to reach placing form.

Closest papers

Nearest neighbours by meaning across the whole index.

An advancing-ridge approach for recovering boundary $(d-1)$-simplices in $d$-dimensional meshes

cs.CE cs.CG ·2026-08-15 ·Philip Caplan
similarity 0.60
Abstract

Boundary-conforming four-dimensional meshes are essential for being able to run spacetime numerical simulations about complex, moving three-dimensional geometries. Specifically, a mesh of pentatopes is needed in which the tetrahedral faces of this mesh conform to the boundary of the domain. In the three-dimensional setting, a common approach consists of generating a constrained Delaunay tetrahedralization. Implementations of this approach are mature, but it is unclear how it extends to the four-dimensional setting, particularly in how the local mesh operations are scheduled to recover the constraints. This paper develops a new algorithm for recovering boundary constraints which is simple to implement in any dimension. The algorithm is primarily an advancing-front approach and uses a constrained cavity operator to incrementally insert constraints into the mesh. Compared to existing advancing-front approaches, which advance from a front of $(d-1)$-simplices (faces), the proposed approach advances from a front of $(d-2)$-simplices, called ridges. Steiner vertices can be added to the boundary when the front stalls and several examples in $3d$ demonstrate the ability of this algorithm to recover a complete representation of the input surface. For the four-dimensional geometries studied here, the algorithm generally recovers at least 99% of the input tetrahedralization with this advancing ridge procedure. For some simpler domains, complete conformity with the input tetrahedralization is achieved by adding Steiner vertices, thereby demonstrating the ability to produce boundary-conforming four-dimensional meshes. The design and efficiency of the underlying cavity operator implementation is also evaluated, showing that 30 million pentatopes can be created in about 1.5 minutes, and 300 million pentatopes in about 15 minutes on a workstation laptop.

0.04

Multiform Longest Edge Bisection of Tetrahedra via Sextuple Permutations

cs.CG math.NA ·2026-09-22 ·Agustin Trujillo, Jose Pablo Suarez, Tania Moreno-García
theory similarity 0.59
Abstract

We introduce a new formulation of the Longest Edge Bisection (LEB) of tetrahedra entirely in sextuple space R6, where tetrahedra are represented by the squares of their edge lengths. This representation renders the LEB refinement equations fully linear and eliminates the need for coordinate-based data structures. A central difficulty in three-dimensional LEB arises when a tetrahedron possesses multiple longest edges, making the refinement rule intrinsically multivalued. We formalize this phenomenon through the notion of Multiform Longest Edge Bisection (MLEB), which systematically explores all admissible longest-edge choices. To encode this multivalued behavior, we introduce the concept of bisection patterns, defined as sequences of sextuple permutations governing the refinement process. We prove that the set of sextuples sharing a common LEB pattern forms a convex region in R6. For structurally significant families of tetrahedra, including the R1+ family and the Liu-Joe family, we show that the infinite refinement tree collapses into a finite directed graph with eight states. Remarkably, both families are governed by the same graph, differing only in their initial state. This directed-graph formulation provides a unified combinatorial description of the refinement process and offers an efficient computational framework for deep iterative LEB analysis.

0.46

Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees

cs.CG math.CO ·2026-11-03 ·Oswin Aichholzer, Joseph Dorfer, Peter Kramer, Christian Rieck, Birgit Vogtenhuber
similarity 0.59
Abstract · 17 pages, 5 figures, 5 tables

We study the problem of reconfiguring plane, straight-line spanning trees on point sets in the plane. A flip is a reconfiguration step in which one edge of a tree is replaced with another, yielding again a plane spanning tree. For a given point set $P$, the flip graph has a vertex for each plane spanning tree on $P$, and an edge between any two trees that differ by a single flip. The folklore happy edge conjecture suggests that any edge shared by both the initial and the target tree (a happy edge) is never flipped in a shortest flip sequence. This conjecture was computationally verified for up to 10 points in convex position. In this paper, we disprove this conjecture both on general point sets and on point sets in convex position by providing two counterexamples on $16$ and $30$ points, respectively. The counterexample for point sets in general position also holds for compatible flips, while the happy edge property holds for compatible flips in convex point sets as shown by Aichholzer, Dorfer, and Vogtenhuber [GD 2025].

0.21

On the Spanning Ratio of the Greedy Triangulation for Convex Point Sets

cs.CG ·2026-08-10 ·Prosenjit Bose, Jean Lou de Carufel, Anil Maheshwari, Bobby Miraftab, Michiel Smid +1 more
theory similarity 0.59
Abstract

The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an earlier one. Its spanning ratio is known to be bounded by a universal constant, but the standard bound obtained from the diamond and good-polygon properties is about $11739.1$. We prove a substantially smaller bound for points in convex position. In particular, for every finite point set $P\subset\mathbb{R}^2$ in convex position and every pair $u,v\in P$, the greedy triangulation contains a $u$--$v$ path of length at most $κ|uv|$, where $κ<17.814$. Thus, the greedy triangulation of a convex point set is an $18$-spanner.

0.04

The Stretch Factor of Planar Delaunay Triangulations Is Nearly Determined

cs.CG ·2026-09-07 ·Guanlin Mo, Kangke Cheng, Hu Ding
theory similarity 0.58
Abstract · 67 pages, 14 figures, 8 tables. Substantially revised: the upper bound is improved from 1.65 to 1.5949, and the title has changed. Verificat…

The Delaunay triangulation is a classical geometric structure on a finite set of points in the plane. Its stretch factor is the largest ratio of the shortest-path distance along its edges to the Euclidean distance between the same two points. Determining the worst-case stretch factor of planar Delaunay triangulations is a long-standing open problem. We prove a uniform upper bound of 1.5949, improving the previous bound of 1.998 and narrowing the gap to the best known lower bound of 1.5932 from 0.4048 to less than 0.0017, nearly pinpointing the worst-case stretch factor. A central difficulty is that the line segment between two points may cross arbitrarily many triangles. Our progress accounting framework addresses this by converting the global bound into a family of local inequalities, each involving only a fixed number of real parameters regardless of the number of triangles crossed. Two further geometric lemmas make computer-assisted verification tractable: the pencil lemma decomposes each local transition into two geometrically independent stages, reducing verification over infinitely many possible next disks to a single differential condition; and the corner lemmas handle degenerate boundary cases where direct verification would fail. With these reductions, the proof ends with a finite verification of an explicit potential in exact rational arithmetic and outward-rounded interval arithmetic. Numerous geometric network constructions use the Delaunay stretch factor as a black box, so the tighter bound directly improves stretch-factor guarantees for a range of downstream applications, including bounded-degree plane spanners and low-weight spanners.

0.29

Computing an e-net of a closed hyperbolic surface

cs.CG math.GT ·2026-08-25 ·Vincent Delecroix, Vincent Despré, Camille Lanuel, Hugo Parlier, Monique Teillaud
similarity 0.58
Abstract

Hyperbolic surfaces are a fundamental object in mathematics and play an increasingly important role in computational geometry and topology. A key ingredient in the design of efficient algorithms on such surfaces is the availability of a geometric discretization of controlled complexity. In this paper, we present the first algorithm for constructing e-nets on hyperbolic surfaces starting from a fundamental polygon representation. Our approach is based on Delaunay refinement and relies on maintaining Delaunay triangulations through edge flips. The size of an e-net cannot be bounded solely as a function of the genus because of the presence of arbitrarily long collars around short geodesics. To overcome this difficulty, we introduce the notion of a pseudo e-net, which decomposes the surface into e-thin cylinders together with a Delaunay triangulation over an e-net of the remaining thick part. As applications, we obtain algorithms for computing the length spectrum of an e-thick hyperbolic surface and for computing the systole from a pseudo log(sqrt(2))-net. These results demonstrate that Delaunay-based discretizations provide a practical and versatile framework for algorithmic computations on hyperbolic surfaces.

0.45

A Collapse Process for Farthest Voronoi Diagrams of Lines in Three Dimensions

cs.CG ·2026-09-24 ·Evanthia Papadopoulou, Martin Suderland, Zeyu Wang
similarity 0.58
Abstract

We study a \emph{collapse process} to construct the farthest Voronoi diagram of lines in three dimensions, given a spherical map of the diagram's unbounded features. The collapse process sweeps through the diagram in order of decreasing distance from the farthest lines. It follows the \emph{shrinking map}, a cell complex on a topological sphere that encodes the locus of points with a fixed farthest distance. We show that, in three dimensions, the collapse process has exactly four non-terminal local event types that change the structure of the shrinking map: \emph{deletion, swap, local minimum}, and \emph{local maximum} events; plus one terminal event. This list is complete. We give intrinsic three-dimensional geometric descriptions of the four non-terminal events. First, we classify the two vertex-related events, deletion and swap events, by the spherical convex hull of the four tangent points from a vertex to its four defining lines. Then, we analyze the events related to the local extrema of the distance function along the trisector of three lines. We show that the distance function along a trisector has at most $4$ local maxima and $8$ local minima, and that both bounds are tight. The extrema can be found via a polynomial of degree $12$. As a byproduct, this gives a direct method for finding the smallest sphere tangent to three given lines. At each local extremum, the tangent sphere touches the three lines at points lying on a great circle. The collapse process and the completeness of the event list also apply, under similar general position assumptions, to the farthest Voronoi diagram of convex sites under strictly convex distance functions.

0.37

Connectivity Augmentation of Plane Graphs

cs.DS ·2026-08-11 ·Krishnan Dehaleesan, Asif Khan, Pranabendu Misra
published similarity 0.58
Abstract · Accepted for publication in MFCS 2026. 29 pages, 4 figures

We study the problem of connectivity augmentation of a planar graph, while preserving planarity. This problem is motivated by many real-world settings such as road-networks, power-networks etc. In these settings, it is crucial to preserve the original planar embedding after augmentation. In 2009, Gutwenger and Mutzel gave a constructive algorithm showing that a connected planar graph with a fixed embedding (a plane graph) can be optimally augmented to a biconnected graph without crossings while preserving the embedding. We further this line of research, by giving an algorithm that computes a minimum set of edges that makes a connected plane graph 2-edge-connected in \(O(|V|(1+α(|V|)))\) time and linear space, where \(α\) is the inverse Ackermann function.

0.29