computational geometry engineers

Abstract: A polychromatic $2$-coloring of a triangulation is a $2$-coloring of the vertices such that no face is monochromatic. The discrepancy of a coloring is the maximum difference between the sizes of the color classes. Asayama and Matsumoto (Graphs and Combinatorics, 2022) proved that every triangulation admits a polychromatic $2$-coloring with discrepancy at most $\tfrac{5n-16}{9}$, and that there exists a class of triangulations for which every polychromatic $2$-coloring has discrepancy at least $\tfrac{n}{3} - 2$, where $n$ is the number of vertices. We improve the upper bound, showing that every triangulation admits a polychromatic $2$-coloring with discrepancy at most $\tfrac{3n-16}{7}$ and such a $2$-coloring can be computed in quadratic time. We also show a discrepancy of at most $n-\tfrac{4M}{3}$ for triangulations with a matching of size $M$. This implies, for example, that Delaunay triangulations admit a discrepancy of at most $\tfrac{n}{3}$. We provide a linear-time algorithm to compute a $2$-coloring whose discrepancy is at most $\tfrac{5n-24}{7}$. One of our results shows that any proper four coloring with the largest color class of size $\frac{n}{2}$ would imply a $2$-coloring with discrepancy at most $\frac{n}{3}$. The existence of such a proper coloring has been recently confirmed by Kawarabayashi, Yoneda, and Yoneda (arXiv 2026). Therefore the two results together confirm the discrepancy of at most $\frac{n}{3}$ for triangulations.

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.