Fact-checked by Grok 2 weeks ago

Discrete geometry

Discrete geometry is a branch of geometry that studies the combinatorial properties and constructive methods of discrete geometric objects, such as finite arrangements of points, lines, planes, polyhedra, and lattices in Euclidean space.^[1]^[2] It focuses on the arrangements and interactions of these discrete sets, often emphasizing convexity, packing, covering, and enumeration problems rather than continuous manifolds or curves.^[3] Unlike classical geometry, which deals with smooth and infinite structures, discrete geometry addresses finite or countable configurations, bridging combinatorics and geometry through tools like convex hulls and separation theorems.^[1]^[3] The field has roots in classical problems dating back to the 17th century, such as Johannes Kepler's 1611 conjecture on the densest packing of spheres, which was rigorously proved by Thomas Hales in 1998 and published in 2005.^[1] Key foundational results include Helly's theorem, which states that for a family of convex sets in \mathbb{R}^d, if every d+1 sets have nonempty intersection, then the entire family intersects, providing essential tools for intersection and covering problems.^[2] Other central concepts encompass lattice theory, where integer points in convex bodies are analyzed via theorems like those of Blichfeldt and Minkowski on successive minima and inhomogeneous minima; sphere packings and coverings; and Ehrhart polynomials, which count lattice points in dilates of polytopes.^[1]^[3] These elements often intersect with convex geometry, as seen in Carathéodory's theorem, which asserts that any point in the convex hull of a set in \mathbb{R}^d can be expressed as a convex combination of at most d+1 points from the set.^[3]^[2] Discrete geometry's scope extends to polyhedral and surface structures, including rigidity theory—such as Cauchy's theorem on the congruence of convex polytopes with isometric faces—and topological methods for problems like the four-vertex theorem for curves.^[2] It also incorporates computational aspects, like the shortest vector problem in lattices, which is NP-hard and underlies algorithms such as the LLL reduction used in cryptography.^[1] Applications span diverse fields: in coding theory and telecommunications for optimal sphere packings; in computer graphics and modeling for surface parameterizations and triangulations; in brain imaging for geometric analysis of discrete data; and in theoretical computer science for problems like Siegel's lemma in Diophantine approximation.^[1]^[4] Recent developments continue to explore connections to graph theory, Ricci flows on discrete surfaces, and statistical methods for ranking via combinatorial Hodge theory.^[4]

Introduction and Foundations

Definition and Scope

Discrete geometry is a branch of mathematics that investigates geometric objects and configurations through the lens of discrete mathematics, prioritizing combinatorial, topological, and algebraic techniques rather than continuous analytic methods.^[5] It examines finite or countable structures embedded in Euclidean or other spaces, focusing on their qualitative properties and relationships.^[6] This approach contrasts with classical geometry by avoiding infinitesimal considerations, instead leveraging tools like graph theory and enumeration to uncover patterns and invariants.^[7] Central to discrete geometry are characteristics such as finite point sets in the plane or higher dimensions, configurations with integer coordinates like lattices, and arrangements that may dispense with metric assumptions to emphasize combinatorial types.^[5] The field stresses problems of existence, enumeration, and classification, often asking how many such objects satisfy certain conditions or what their extremal properties are.^[6] Representative examples include finite sets of points in general position in the plane, where no three are collinear, and integer lattice points within convex regions.^[1] Polyhedral arrangements, such as those formed by hyperplanes, illustrate how discrete structures partition space into cells with countable complexity.^[8] Discrete geometry overlaps considerably with combinatorial geometry and geometric combinatorics.^[7] The scope of discrete geometry excludes purely continuous phenomena, such as smooth curves without discretization, but incorporates approximations or finite samplings of continuous objects, like lattice points approximating a circle.^[5] This includes the geometry of numbers, pioneered by Hermann Minkowski, which applies discrete methods to number-theoretic problems involving lattice points in convex bodies.^[3]

Relation to Continuous Geometry

Discrete geometry fundamentally differs from classical continuous geometry in its foundational assumptions and analytical tools. While continuous geometry operates on smooth manifolds using limits, derivatives, and measure theory to describe properties like curvature and volume, discrete geometry focuses on finite or countable sets of points, lines, and polygons, employing combinatorial invariants such as counts of vertices, edges, and faces to analyze structure and incidence relations.^[9] This dichotomy arises from the discrete nature of combinatorial counting versus the infinite divisibility of continuous spaces, where phenomena like incommensurability highlight the irreducibility of continuous quantities to discrete units.^[9] Discretization processes bridge these domains by approximating smooth curves and manifolds with discrete representations, such as polygonal meshes or point clouds, to enable computational analysis while preserving key geometric features. For curves, sample points are connected via piecewise linear segments, often refined through subdivision schemes to approach smoothness; for surfaces, point clouds derived from scans are triangulated using algorithms like Delaunay triangulation or the Ball-Pivoting method, converting continuous data into connected polygonal facets that approximate the original manifold's topology and metric properties.^[10] These approximations introduce finite resolution, allowing discrete methods to simulate continuous behaviors but at the cost of exact differentiability. Notable bridges between the fields include the Euler characteristic \chi = V - E + F, where V, E, and F denote vertices, edges, and faces, serving as a discrete topological invariant analogous to the continuous Gauss-Bonnet theorem, which relates total Gaussian curvature to \chi via integration over the surface.^[11] In discrete settings, variants of the Gauss-Bonnet theorem equate sums of local discrete curvatures—defined, for instance, as angle deficits at vertices or deviations from flatness in meshes—to multiples of \chi, mirroring how continuous Gaussian curvature integrates to $2\pi \chi for closed surfaces.^[11] Discrete curvature notions further extend this analogy, approximating continuous principal or mean curvatures through finite differences on meshes, such as cotangent-based Laplacians that converge to the smooth Laplace-Beltrami operator under mesh refinement.^[12] However, discretization imposes limitations, notably the loss of smoothness that engenders rigidity in discrete structures compared to the flexibility of continuous ones. In continuous geometry, deformations can occur smoothly along infinite degrees of freedom, whereas discrete frameworks, like bar-joint structures, often exhibit combinatorial rigidity, where infinitesimal motions are constrained by incidence relations, preventing flexible deformations without breaking constraints.^[13] This rigidity manifests in phenomena like the generic rigidity of graphs in \mathbb{R}^d, contrasting with the continuous case's allowance for non-trivial deformations in underconstrained manifolds.^[13] An illustrative example is optimization in packing problems, where discrete approaches restrict object positions to lattices or finite configurations, yielding exact but computationally intensive solutions via enumeration, while continuous formulations permit real-valued translations and rotations, enabling gradient-based optimization but introducing challenges like non-convexity and local minima not present in purely discrete variants.^[14] Polyhedra serve briefly as discrete analogs of curved surfaces in such contexts, approximating spheres or tori through faceted approximations.^[10]

Historical Development

Early Origins

The foundations of discrete geometry can be traced to ancient Greece, where early explorations of geometric structures laid the groundwork for combinatorial and discrete approaches. In his Elements (circa 300 BCE), Euclid systematically described the five regular polyhedra—tetrahedron, cube, octahedron, dodecahedron, and icosahedron—proving their existence and properties as convex bodies bounded by congruent regular polygons, which anticipated later studies in polyhedral combinatorics. Euclid also examined plane tilings through constructions of regular polygons and their arrangements, such as equilateral triangles and squares, establishing principles of tessellation that influenced discrete spatial divisions without continuous variation. During the Renaissance, discrete geometric ideas gained prominence through influential conjectures and projective configurations. In 1611, Johannes Kepler proposed what became known as Kepler's conjecture, asserting that the face-centered cubic lattice achieves the densest packing of equal spheres in three-dimensional space, with a density of \pi / (3\sqrt{2}) \approx 74.05\%, marking an early discrete optimization problem in packing. Around the same period, Girard Desargues introduced the Desargues configuration in his 1639 Brouillon project d'une atteinte aux événements des rencontres du cône avec un plan, a finite incidence structure of 10 points and 10 lines in the projective plane where each line contains 3 points and each point lies on 3 lines, highlighting combinatorial symmetries that bridged projective geometry and discrete configurations.^[15] The 19th century saw discrete geometry emerge as a distinct field, with rigorous theorems on rigidity and packing. In 1813, Augustin-Louis Cauchy proved his rigidity theorem, stating that a convex polyhedron with rigid faces cannot be continuously deformed while preserving edge lengths, implying uniqueness in shape up to congruence for given facial structures—a foundational result in structural combinatorics.^[16] Concurrently, combinatorial aspects arose from map coloring problems; in 1852, Francis Guthrie conjectured that four colors suffice to color any planar map so that adjacent regions differ in color, originating from observations of English county maps and sparking early graph-theoretic inquiries into discrete embeddings.^[17] Toward century's end, Axel Thue advanced packing theory in his 1892 work, demonstrating that the hexagonal lattice provides the densest packing of equal circles in the plane, with density \pi / \sqrt{12} \approx 90.69\%, using finite approximations to bound infinite arrangements and solidifying discrete methods over continuous ones.^[18] These contributions by Kepler, Cauchy, and Thue marked a transition from classical Euclidean geometry to a focus on finite, countable structures, setting the stage for modern discrete geometry.

Modern Advances

In the early 20th century, Hermann Minkowski developed the geometry of numbers, introducing fundamental concepts such as the Minkowski theorem on convex bodies and lattice points, which provided tools for analyzing Diophantine approximation and integer programming problems. His work from 1896 to 1910 laid the groundwork for applying geometric methods to number theory, emphasizing the volume of convex sets in Euclidean space to bound the existence of non-trivial integer solutions. By the 1940s, László Fejes Tóth advanced the field through his theorems on circle packings and densest packings of convex bodies, providing a rigorous proof that the densest packing of equal circles in the plane achieves a density of \pi / \sqrt{12}, as in the hexagonal lattice. These results, detailed in his works from the 1940s and his 1950 monograph Lagerungen in der Ebene, auf der Kugel und im Raum, extended classical packing problems and influenced subsequent work on sphere packings in higher dimensions.^[19] Mid-century developments included Harold Scott MacDonald Coxeter's systematic classifications of finite polytopes and reflection groups, culminating in his 1950 book Regular Polytopes, which enumerated all regular polytopes in dimensions up to four and their generalizations. Coxeter's work formalized the combinatorial structure of these objects using Coxeter-Dynkin diagrams, bridging geometry with group theory. Concurrently, Paul Erdős posed numerous problems in extremal graph theory with geometric interpretations, such as the unit distance problem and happy ending problem, from the 1950s through the 1980s, stimulating research on incidences between points and lines in the plane. The late 20th century saw a boom in topological combinatorics, highlighted by László Lovász's 1978 proof of the Kneser conjecture using the Borsuk-Ulam theorem, which resolved the chromatic number of Kneser graphs and advanced understanding of graph colorings via topological methods. In the 1980s, oriented matroids were formalized as a combinatorial abstraction of point configurations, culminating in the 1993 book Oriented Matroids by Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, providing a framework for studying sign patterns and chirotopes without embedding in Euclidean space.^[20] Entering the 21st century, computational breakthroughs enabled software tools for analyzing rigidity in bar-and-joint frameworks, such as the Rigid Component Decomposition package developed post-2000, which computes generic rigidity in the plane using pebble games and matroid algorithms. These tools have facilitated verification of large-scale structures in architectural design and materials science. Post-2020 advances include discrete Ricci flow methods for mesh smoothing in computational geometry, as explored in works adapting Perelman's Ricci flow to polygonal surfaces for curvature equalization without singularities. As of 2025, the Hadwiger conjecture remains unsolved, though partial results have confirmed it for graphs up to 6 colors, with ongoing efforts using topological and spectral methods.

Combinatorial Structures

Polyhedra and Polytopes

A convex polyhedron is a three-dimensional body that is the bounded intersection of a finite number of half-spaces in Euclidean space \mathbb{R}^3.^[21] More generally, an n-dimensional polytope (or convex polytope) is the convex hull of a finite set of points in \mathbb{R}^n, or equivalently, the bounded intersection of finitely many half-spaces; these objects generalize polyhedra to higher dimensions.^[22] Polytopes are the fundamental building blocks in discrete geometry for studying combinatorial and geometric properties of convex bodies. A key relation among the combinatorial elements of polytopes is given by Euler's formula and its higher-dimensional analogs. For a convex polyhedron with V vertices, E edges, and F faces, Euler's formula states V - E + F = 2.^[23] In n dimensions, if f_k denotes the number of k-dimensional faces (for k = 0, \dots, n-1), with f_{-1} = f_n = 1 by convention (accounting for the empty face and the polytope itself), the generalized Euler relation is

\sum_{k=-1}^{n} (-1)^k f_k = 0.

This holds for any convex n-polytope and reflects its topological equivalence to an n-ball. Convex polyhedra and polytopes are classified by their symmetry and uniformity. The five regular polyhedra, known as Platonic solids, are the tetrahedron, cube, octahedron, dodecahedron, and icosahedron; these are the only convex polyhedra where all faces are congruent regular polygons and the same number of faces meet at each vertex.^[24] Archimedean solids extend this to 13 semi-regular polyhedra that are vertex-transitive (all vertices equivalent under symmetry) but have regular polygonal faces of more than one type.^[25] Uniform polytopes in higher dimensions, including regular and Archimedean types, are compactly described using Schläfli symbols \{p_1, p_2, \dots, p_{n-1}\}, where each p_i indicates the number of sides of the faces meeting at successive levels of the structure; for example, the cube has symbol \{4,3\}.^[26] Combinatorial types of polytopes are captured by their f-vectors, which record the number of faces of each dimension: the f-vector of an n-polytope is (f_0, f_1, \dots, f_{n-1}), where f_k is the number of k-faces.^[27] These vectors satisfy the Euler relation and additional inequalities, such as those from the Dehn-Sommerville equations for simplicial or simple polytopes. Two seminal theorems characterize extremal properties: Steinitz's theorem states that a graph is the 1-skeleton of a convex 3-polyhedron if and only if it is planar and 3-connected.^[28] The upper bound theorem, proved by McMullen, asserts that the maximum number of k-faces of an n-polytope with v vertices is achieved by the cyclic polytope, providing tight bounds like f_{n-1} \leq \binom{v}{\lfloor n/2 \rfloor} + \binom{v}{\lceil n/2 \rceil - 1} for facets. Representative examples illustrate these concepts. The cube is a Platonic solid with 8 vertices, 12 edges, 6 square faces, and f-vector (8,12,6); it satisfies Euler's formula as $8 - 12 + 6 = 2. The regular dodecahedron has 20 vertices, 30 edges, and 12 pentagonal faces, with f-vector (20,30,12). In four dimensions, the tesseract (or 4-cube) is a regular 4-polytope with Schläfli symbol \{4,3,3\}, 16 vertices, 32 edges, 24 square faces, and 8 cubic cells, satisfying the generalized Euler relation -1 + 16 - 32 + 24 - 8 + 1 = 0.^[29]

Packings, Coverings, and Tilings

In discrete geometry, a packing is an arrangement of geometric objects, such as disks or spheres, in Euclidean space such that their interiors do not overlap, while a covering ensures that the union of the objects contains the entire space without gaps. A tiling achieves both conditions simultaneously, partitioning the space into non-overlapping objects that cover it completely, and may be periodic (repeating translationally) or aperiodic (lacking such repetition). These concepts are central to studying efficient spatial arrangements, often measured by density metrics.^[30] The packing density \delta of a packing P in \mathbb{R}^n is defined as

\delta(P) = \limsup_{r \to \infty} \frac{\vol(B_r \cap P)}{\vol(B_r)},

where B_r is the ball of radius r centered at the origin and \vol denotes Lebesgue measure; this captures the asymptotic volume fraction occupied by the objects. Similar notions apply to covering density, defined analogously but using the infimum over minimal volumes needed to cover B_r. These densities quantify efficiency, with upper bounds often derived from combinatorial or analytic arguments. A landmark result is the Kepler conjecture, which states that the maximum packing density for equal spheres in three-dimensional space is \delta \leq \pi / \sqrt{18} \approx 0.7405, achieved by the face-centered cubic lattice arrangement. This was proved by Thomas Hales in 1998 using computer-assisted enumeration of Voronoi cells, with the proof published in 2005 and formally verified in 2014. In two dimensions, Thue's theorem establishes that the densest packing of equal circles is the hexagonal lattice, with density \delta = \pi / \sqrt{12} \approx 0.9069; originally claimed in 1892 and rigorously proved in 1910, a simple modern proof relies on Delaunay triangulations to bound local densities.^[31]^[32]^[33] Tilings extend these ideas to exact partitions, with notable examples including aperiodic sets that admit tilings of the plane but none that are periodic. The first such set of Wang tiles—unit squares with colored edges that must match adjacently—was constructed by Robert Berger in 1966, containing over 20,000 tiles and linking aperiodicity to the undecidability of the domino problem. Roger Penrose later developed simpler aperiodic tilings in 1974 using two rhombi with angles of $72^\circ and $144^\circ, enforced by matching rules that force fivefold symmetry and forbid periodicity; these exhibit self-similar inflation rules generating hierarchical patterns. In 2023, mathematicians discovered an aperiodic monotile, known as "the hat," a single 13-sided shape that tiles the plane aperiodically through geometry alone, without needing reflections or additional matching rules; this resolved a long-standing conjecture for an "einstein" tile.^[34] For coverings, László Fejes Tóth established foundational theorems on thinnest arrangements, such as bounds for covering the plane with congruent disks where the minimal density exceeds that of lattice coverings in certain cases. In his 1950 work, he proved results like the inefficiency of certain hexagonal coverings, showing that the thinnest covering density for equal circles is approximately 1.209, achieved by the hexagonal lattice arrangement. These theorems often use Blichfeldt-type inequalities to derive lower bounds on covering densities. Lattice-based packings and coverings provide periodic benchmarks but are frequently suboptimal compared to these general results.^[35]^[36]

Geometric Graph Theory

Geometric graph theory is a branch of discrete geometry that examines graphs embedded in Euclidean spaces, particularly the plane or higher dimensions, where vertices are represented by points and edges by straight-line segments connecting them. These embeddings, known as straight-line drawings, preserve the combinatorial structure of the graph while incorporating geometric constraints such as non-crossing edges or minimized intersections. The field explores properties like planarity, crossing minimization, and intersection patterns, bridging combinatorial graph theory with geometric realizations.^[37] A central topic is the study of planar graphs, which admit embeddings in the plane without edge crossings. Fáry's theorem establishes that every simple planar graph has a straight-line embedding that is crossing-free, meaning it can be drawn with vertices as points and edges as line segments without intersections. This equivalence between combinatorial planarity and geometric straight-line planarity simplifies algorithmic constructions of planar drawings. Complementing this, Kuratowski's theorem provides a forbidden subgraph characterization: a graph is planar if and only if it contains no subgraph homeomorphic to the complete graph K_5 or the complete bipartite graph K_{3,3}. These results ensure that planarity tests can yield geometrically realizable outputs.^[38]^[39] For non-planar graphs, the crossing number cr(G) quantifies the minimal number of edge crossings in any drawing of G in the plane, often using straight-line edges in geometric contexts. Determining cr(G) is NP-hard, but the crossing lemma provides a fundamental lower bound: for a simple graph G with n vertices and m edges where m \geq 4n, cr(G) \geq c \frac{m^3}{n^2} for some constant c > 0 (originally c = \frac{1}{64}). This inequality, proved using probabilistic methods on random subgraphs, reveals how dense graphs inevitably require many crossings and has implications for extremal graph theory.^[40] Unit disk graphs form another key class, defined as intersection graphs where vertices correspond to points in the plane and edges exist between points at distance at most 1 (or equivalently, intersections of unit-radius disks centered at those points). These graphs model wireless ad-hoc networks, where nodes communicate if within transmission range, and possess properties like bounded chromatic number (at most 3 for triangle-free instances) that aid in scheduling and coloring problems. Recognizing whether a graph is a unit disk graph is NP-hard, highlighting computational challenges in geometric realizations. The geometric thickness of a graph measures the minimal number of planar straight-line layers needed to partition its edges such that each layer is crossing-free. For complete graphs K_n, it lies between \lceil n/5.646 \rceil + 0.342 and \lceil n/4 \rceil, with exact values known for small n. Graphs of maximum degree at most 4 have geometric thickness 2, enabling efficient layered drawings. This parameter extends planarity to denser graphs and supports multi-layer representations.^[41]^[42] Applications of geometric graph theory abound in practical domains. In VLSI design, minimizing crossings in straight-line layouts optimizes circuit routing and reduces wire lengths, leveraging crossing number bounds to assess feasibility. Similarly, map labeling algorithms use non-crossing straight-line drawings to position text without overlaps, ensuring readability in cartographic visualizations. These techniques also inform wireless network topology design by modeling interference via unit disk intersections.^[43]^[44]

Incidence and Abstract Structures

Incidence Structures

An incidence structure is a mathematical framework consisting of a set of points P, a set of lines L, and an incidence relation I \subseteq P \times L that specifies which points lie on which lines, often formalized as a triple (P, L, I).^[45] This abstract setup captures the essential relational data between points and lines without embedding in a metric space, serving as the foundation for various finite geometries in discrete geometry.^[46] Common axioms include the requirement that any two distinct points are incident with at most one line and any two distinct lines are incident with at most one point, ensuring a partial linear space structure.^[46] Projective planes represent a key class of incidence structures where every pair of distinct points determines a unique line, every pair of distinct lines intersects in a unique point, and each line contains the same number of points as each point lies on lines.^[47] For a projective plane of order n (where n \geq 2), there are exactly n^2 + n + 1 points and the same number of lines, with each line incident to n + 1 points.^[47] The smallest such structure is the Fano plane, a projective plane of order 2 with 7 points and 7 lines, each line containing 3 points, and it satisfies the property that any two points determine a unique line while any two lines intersect at a unique point.^[48] Affine planes extend incidence structures by incorporating parallelism: they consist of points and lines where any two distinct points determine a unique line, but lines may be parallel (non-intersecting), partitioned into parallel classes.^[49] In an affine plane of order n, there are n^2 points and n(n + 1) lines, with each line containing n points and each parallel class containing n lines covering all points.^[49] Desargues' theorem in this context asserts that for two triangles in perspective from a point, the intersections of corresponding sides are collinear, providing a coordinatization condition equivalent to the plane being embeddable over a division ring.^[49] Block designs generalize incidence structures to combinatorial settings, where points and blocks (subsets analogous to lines) satisfy balanced incidence properties. A balanced incomplete block design (BIBD) is an incidence structure (X, B) with v = |X| points, b = |B| blocks each of size k, such that every point appears in r blocks and every pair of distinct points is contained in exactly \lambda blocks, with relations b k = v r and \lambda (v - 1) = r (k - 1).^[50] Projective planes of order n are symmetric BIBDs with v = b = n^2 + n + 1, k = r = n + 1, and \lambda = 1.^[50] The Bruck–Ryser–Chowla theorem imposes necessary conditions on the existence of projective planes: if n \equiv 1 or $2 \pmod{4} and the square-free part of n is divisible by a prime congruent to $3 \pmod{4}, then no projective plane of order n exists.^[51] This theorem rules out planes for orders like 6 and 14, highlighting the scarcity of such structures beyond prime power orders.^[51] Examples of non-projective incidence structures include the Möbius plane, an incidence structure (S, X) of points S and circles X where any three distinct points determine a unique circle, any point outside a circle touches it at exactly one point via a unique tangent circle, and no four points are concyclic unless specified.^[52] The near-pencil configuration is a degenerate linear space with one line containing k-1 points for k \geq 3, and additional lines each connecting the k-th point to one of the others, ensuring any two points lie on a unique line while most points are collinear.^[53]

Oriented Matroids

Oriented matroids provide a combinatorial framework that extends the concept of matroids by incorporating orientation information, specifically capturing the sign patterns arising from linear dependencies in real vector configurations. Formally, an oriented matroid on a finite ground set E is defined via its covectors, which are sign vectors in \{-, 0, +\}^E representing the separation of elements by hyperplanes. These covectors encode the positive, negative, and zero parts relative to affine dependencies, abstracting the oriented circuits of the underlying matroid where circuits are minimal dependent sets with assigned signs indicating direction.^[54] The axiomatic structure for covectors consists of four key properties: (CV0) the zero vector is a covector; (CV1) if X is a covector, so is its negation -X; (CV2) the coordinatewise composition X \circ Y, defined by taking the nonzero entry from X when possible and otherwise from Y, is a covector; and (CV3) a separation axiom ensuring that if two covectors X, Y differ on an element e with X(e) = + and Y(e) = -, then there exists a covector Z separating them appropriately on the relevant supports. Equivalently, oriented matroids can be axiomatized using chirotopes, which are alternating sign functions \chi: \binom{E}{r} \to \{-, 0, +\} (where r is the rank) satisfying: (CHI1) |\chi| defines the underlying matroid (nonzero on bases), and (CHI2) the Grassmann-Plücker relations hold, ensuring consistency of orientations across bases. For rank 3 oriented matroids, chirotopes correspond to acyclic orientations, while topes—maximal covectors with no zeros—represent the chambers or regions of the arrangement.^[55] Realizable oriented matroids arise directly from geometric configurations, such as points in \mathbb{R}^d, where the chirotope is given by \chi(X) = \operatorname{sign} \det(x_{\lambda_1}, \dots, x_{\lambda_d}) for a basis X = \{\lambda_1, \dots, \lambda_d\}, capturing the oriented volume. Not all oriented matroids are realizable over the reals, but the topological representation theorem guarantees that every oriented matroid of rank d can be represented by an arrangement of oriented pseudohyperplanes on the (d-1)-sphere, where pseudohyperplanes are homeomorphic images of great hyperspheres satisfying certain intersection properties. For uniform oriented matroids, where the underlying matroid is uniform (every r-subset is a basis), this theorem implies a simple pseudosphere arrangement without multiple intersections.^[56] Key theorems underscore the richness of this structure; the topological representation theorem, originally proved by Folkman and Lawrence, links combinatorial axioms to topological realizations and has been refined for algorithmic purposes. Uniform oriented matroids are particularly well-studied, as they model generic positions in arrangements and admit explicit constructions via cyclic permutations.^[57] Applications of oriented matroids abound in discrete geometry, notably in pseudoline arrangements, where rank-3 oriented matroids encode non-stretchable configurations like the Pappus arrangement realized over pseudolines rather than straight lines. They also describe zonotopal tilings, where the covector lattice governs the face structure of zonotopes and their subdivisions, facilitating the study of translation polytopes. Oriented matroids find use in rigidity analysis of bar-joint frameworks by modeling oriented dependencies in tensegrity structures.^[54] A representative example is the alternating matroid on six elements \{1,2,3,4,5,6\} of rank 3, derived from orientations in the complete graph K_6, where the chirotope assigns \chi(1,4,6) = - and alternates signs based on permutation parity in a cyclic configuration, illustrating a non-realizable uniform oriented matroid that violates real embeddability yet satisfies the axioms.^[55]

Simplicial Complexes

A simplicial complex is a fundamental structure in discrete geometry and combinatorial topology, consisting of simplices glued together in a controlled manner. An abstract simplicial complex K is defined as a finite collection of finite sets, called simplices, that is closed under taking subsets: if \sigma \in K and \tau \subseteq \sigma, then \tau \in K. The elements of the sets in K form the vertex set V(K), and the maximal simplices are termed facets. This combinatorial abstraction allows for the study of topological properties without immediate reference to embedding in Euclidean space. The geometric realization |K| of an abstract simplicial complex K is obtained by associating to each simplex \sigma \in K a standard geometric simplex \Delta^\sigma of the same dimension and gluing them along shared faces via affine homeomorphisms, ensuring that the resulting space is a topological space homeomorphic to the union of these simplices. This realization provides a concrete topological space whose properties, such as connectivity and homology, can be computed combinatorially from K. A k-simplex in K is a set of k+1 vertices, and the dimension of K is the maximum dimension of its simplices; a complex is pure if all facets have the same dimension, which simplifies certain analytical tasks in discrete geometry. Local structure in simplicial complexes is captured by the star and link operators. The closed star \overline{\mathrm{st}}(\sigma) of a simplex \sigma \in K comprises all simplices in K that contain \sigma as a face, while the open star \mathrm{st}(\sigma) excludes the boundaries of those simplices. The link \mathrm{lk}(\sigma) consists of all simplices \tau \in K such that \tau \cap \sigma = \emptyset but \tau \cup \sigma \in K, providing a combinatorial description of the "neighborhood" around \sigma without including it. These operators are essential for analyzing local topology, such as determining if a complex models a manifold locally.^[58] Key theorems highlight the interplay between combinatorial and topological aspects of simplicial complexes. The simplicial approximation theorem states that for finite simplicial complexes K and L, any continuous map f: |K| \to |L| is homotopic to a simplicial map \overline{f}: K \to L after sufficiently fine barycentric subdivision of K, enabling the computation of homotopy groups via simplicial methods. The Hauptvermutung, conjecturing that homeomorphic polyhedra admit combinatorially equivalent triangulations, was resolved negatively: John Milnor constructed two finite 2-dimensional simplicial complexes that are homeomorphic but not combinatorially equivalent, even after subdivision.^[59] Prominent examples include the boundary complex \partial \Delta^n, which is a pure (n-1)-dimensional simplicial complex homeomorphic to the (n-1)-sphere, consisting of all proper faces of the n-simplex \Delta^n. Delta-complexes generalize simplicial complexes by allowing multiple simplices to attach along the same face map, reducing the number of simplices needed for certain realizations while preserving chain homotopy equivalence to their simplicial counterparts; for instance, the torus can be modeled as a Delta-complex with just one 0-simplex, three 1-simplices, and two 2-simplices. These structures find application in topological combinatorics for enumerating complexes with prescribed properties.

Topological and Algebraic Aspects

Topological Combinatorics

Topological combinatorics employs tools from algebraic topology, such as simplicial homology and cohomology, to address enumeration problems in discrete geometric structures, enabling the computation of topological invariants like Betti numbers for complexes arising from combinatorial objects.^[60] These invariants capture the number of "holes" in various dimensions, providing insights into connectivity and higher-dimensional features that traditional counting methods overlook. For instance, homology groups H_i(K) of a simplicial complex K quantify cycles not bounding lower-dimensional ones, while cohomology offers dual perspectives useful for mapping degrees and obstructions in discrete settings.^[61] A seminal result is the Borsuk-Ulam theorem, which asserts that any continuous function from the n-sphere S^n to \mathbb{R}^n maps at least one pair of antipodal points to the same image; this has profound combinatorial implications, such as guaranteeing equitable divisions in discrete point sets via the discrete ham-sandwich theorem. The theorem underpins Lovász's 1978 proof of the Kneser conjecture, establishing that the chromatic number of the Kneser graph KG(n,k)—with vertices as k-subsets of an n-set and edges between disjoint subsets—is n - 2k + 2, by associating the graph to the connectivity of a certain simplicial neighborhood complex and applying Borsuk-Ulam to its homotopy type.^[62] Shellability further facilitates these computations: a pure d-dimensional simplicial complex is shellable if its maximal faces (facets) admit an ordering F_1, \dots, F_m such that for each j, the intersection F_j \cap \left( \bigcup_{i=1}^{j-1} F_i \right) is a nonempty (d-1)-dimensional face, allowing recursive determination of homology and efficient Betti number calculations without full matrix reductions.^[63] The Euler characteristic, defined as \chi(K) = \sum_{i=0}^{\dim K} (-1)^i \beta_i where \beta_i = \dim H_i(K) are the Betti numbers, serves as an alternating sum invariant preserved under homotopy, aiding enumeration in shellable cases by relating face counts to topological features. Illustrative examples include the nerve lemma, which equates the homotopy type of a paracompact space to that of its nerve simplicial complex when the cover has contractible intersections up to dimension r, applicable to discrete covers where intersection patterns reveal global topology from local data.^[61] Similarly, the topological Tverberg theorem generalizes Tverberg's partition result topologically: for prime q and (q-1)(d+1) + 1 points in \mathbb{R}^d, any continuous map from their simplex to \mathbb{R}^d forces the images of q disjoint faces to intersect, impacting discrete partitioning problems.^[64] Post-2020 developments integrate topological combinatorics into topological data analysis for discrete point clouds, where persistent homology tracks evolving Betti numbers across scales in finite sampled sets, enabling robust feature extraction in geometric datasets despite noise.^[65]

Lattices and Discrete Groups

In the context of discrete geometry, a lattice \Lambda in \mathbb{R}^n is defined as a discrete subgroup of \mathbb{R}^n under addition that spans \mathbb{R}^n over \mathbb{R}, equivalently a \mathbb{Z}-module generated by n linearly independent vectors forming a basis for \mathbb{R}^n.^[66] This structure ensures that \Lambda is discrete, meaning every bounded region contains finitely many lattice points, and it possesses a fundamental domain—a parallelepiped or Voronoi cell—of finite volume, which tiles \mathbb{R}^n by translation under the group action.^[67] The determinant \det(\Lambda), or covolume, is the volume of this fundamental domain and measures the "density" of the lattice points.^[68] The geometry of numbers, pioneered by Hermann Minkowski, investigates the distribution of lattice points within convex bodies and provides bounds on their successive minima. The k-th successive minimum \lambda_k(\Lambda, K) of a lattice \Lambda with respect to a $0-symmetric [convex](/page/Convex) body K \subset \mathbb{R}^nis the infimum of scalars\lambda > 0such that\lambda Kcontainsklinearly independent points of\Lambda. Minkowski's second theorem asserts that for such a Kwith [volume](/page/Volume)\vol(K), the product of the successive minima satisfies \lambda_1(\Lambda, K) \cdots \lambda_n(\Lambda, K) \cdot \vol(K) \leq 2^n \det(\Lambda)$, with equality achieved for certain parallelepipeds.^[69] This result quantifies how lattice points "fill" space and has applications in Diophantine approximation and integer programming.^[70] Discrete groups extend lattice concepts to more general Lie groups, particularly in non-Euclidean settings. Fuchsian groups are discrete subgroups of \mathrm{PSL}(2,\mathbb{R}), the group of orientation-preserving isometries of the hyperbolic plane \mathbb{H}^2, acting properly discontinuously with compact quotients in the cocompact case.^[71] These groups generate fundamental domains that tile \mathbb{H}^2 and are classified by their limit sets and parabolic elements.^[72] Crystallographic groups, conversely, are discrete subgroups of the Euclidean motion group \mathrm{E}(n) = \mathbb{R}^n \rtimes \mathrm{O}(n) acting cocompactly on \mathbb{R}^n, incorporating both translations and rotations to model crystal symmetries.^[73] Bieberbach's theorems classify these: every such group \Gamma has a normal translation subgroup T \cong \mathbb{Z}^n of finite index [\Gamma : T], and there are finitely many isomorphism classes of \Gamma up to conjugation by \mathrm{E}(n) in each dimension n.^[74] For a lattice \Lambda, the Voronoi cell V(0; \Lambda) consists of all points in \mathbb{R}^n closer to the origin than to any other lattice point under the Euclidean norm, forming a convex polytope that tiles \mathbb{R}^n by \Lambda-translations.^[75] The facets of V(0; \Lambda) correspond to nearest-neighbor relations among lattice points. The Delaunay triangulation of \Lambda is the dual complex, connecting lattice points whose Voronoi cells share a facet, yielding a simplicial decomposition of \mathbb{R}^n that is periodic with respect to \Lambda.^[76] This triangulation maximizes the minimal angle among simplices and facilitates computations in packing and covering problems.^[77] Prominent examples include the integer lattice \mathbb{Z}^n, generated by the standard basis vectors e_1, \dots, e_n, which has determinant $1and serves as the [canonical model](/page/Canonical_model) for\mathbb{R}^n.[66] Root lattices, arising from root systems of Lie algebras, provide denser structures; the A_nlattice in\mathbb{R}^{n+1}is the [orthogonal complement](/page/Orthogonal_complement) to the all-ones vector in\mathbb{Z}^{n+1}, with roots of length \sqrt{2}and [determinant](/page/Determinant)\sqrt{n+1}.[78] The E_8lattice in\mathbb{R}^8

is the unique even, positive-definite, [unimodular lattice](/page/Unimodular_lattice) of rank &#36;8

, generated by roots of the E_8 Dynkin diagram, achieving the densest sphere packing in eight dimensions, as proved by Maryna Viazovska in 2016.^[78]^[79] These lattices underpin optimal packings, such as the E_8 sphere packing, which attains density \pi^4 / 384.^[80]

Rigidity and Discrete Analogs

Structural Rigidity and Flexibility

Structural rigidity in discrete geometry concerns the stability of bar-joint frameworks, which model structures composed of joints connected by rigid bars of fixed lengths. A framework in \mathbb{R}^d is defined as a pair (G, p), where G = (V, E) is a finite simple graph with vertex set V and edge set E, and p: V \to \mathbb{R}^d is a placement assigning coordinates to each vertex. The framework is rigid if all continuous motions preserving the distances \|p(u) - p(v)\| for each edge \{u, v\} \in E are trivial, meaning they arise solely from isometries of \mathbb{R}^d (translations and rotations).^[81] Infinitesimal rigidity provides a local characterization of rigidity through linear algebra. An infinitesimal motion of (G, p) is an assignment of velocity vectors v: V \to \mathbb{R}^d such that for every edge \{u, v\} \in E, the relative velocity satisfies (p(u) - p(v)) \cdot (v(u) - v(v)) = 0. The space of trivial infinitesimal motions has dimension d|V| - \binom{d+1}{2}, corresponding to the rigid motions of \mathbb{R}^d. The framework is infinitesimally rigid if the only infinitesimal motions are trivial. This condition is captured by the rigidity matrix R(G, p), a |E| \times d|V| matrix whose row for edge \{u, v\} has entries p(u) - p(v) in the columns for u and p(v) - p(u) in those for v, with zeros elsewhere; infinitesimal rigidity holds if the rank of R(G, p) is d|V| - \binom{d+1}{2}. For generic placements p (where coordinates avoid algebraic dependencies), finite rigidity is equivalent to infinitesimal rigidity.^[82]^[81] In the plane (d=2), Laman's theorem gives a combinatorial characterization of generic rigidity. A graph G is generically rigid in \mathbb{R}^2 if and only if |E| = 2|V| - 3 and every subgraph G' induced by a subset of at least two vertices satisfies |E'| \leq 2|V'| - 3. Such minimally rigid graphs are known as Laman graphs and form the bases of the 2-dimensional rigidity matroid. Rigidity in higher dimensions lacks a simple Laman-type condition, but the theory extends through abstract rigidity matroids, where Graver introduced conditions for independence: a set of edges is independent if it spans no overconstrained subgraph in any dimension up to d, ensuring the rigidity matrix has full row rank for generic placements.^[83]^[84] Global rigidity strengthens the notion of rigidity by requiring uniqueness of the realization up to congruence. A framework (G, p) is globally rigid if every other placement p' preserving the edge lengths is congruent to p via an isometry of \mathbb{R}^d. In \mathbb{R}^2, a graph is generically globally rigid if it is 3-connected and redundantly rigid (remains rigid after removing any single edge). In \mathbb{R}^3, necessary conditions for generic global rigidity include redundant rigidity and 4-connectivity, but Hendrickson's conjecture that these suffice was disproved by counterexamples. The precise characterization is that the graph is generically globally rigid if the minimal kernel dimension of the equilibrium stress matrix is 4.^[85] Flexibility arises when frameworks possess non-trivial degrees of freedom. In \mathbb{R}^3, Maxwell's rule provides a necessary counting condition for minimal rigidity: the degrees of freedom are given by f = 3|V| - 6 - |E|, where the framework is expected to be rigid if f = 0 and flexible if f > 0, accounting for the 6 trivial motions (3 translations and 3 rotations). However, this count is insufficient for sufficiency in 3D, as some graphs satisfying it are flexible due to dependencies.^[86] Seminal examples illustrate these concepts. Cauchy's theorem establishes that a convex polyhedron in \mathbb{R}^3, with its facial triangles treated as rigid plates connected by hinged edges, is infinitesimally rigid; equivalently, the edge framework of a triangulated convex polyhedron is rigid. In contrast, non-convex polyhedra can flex: Bricard's octahedra, discovered in 1897, are self-intersecting flexible polyhedra with six vertices and twelve triangular faces that deform continuously while preserving face shapes and edge lengths, providing the first examples of flexible polyhedra in \mathbb{R}^3.^[87]^[88] Rigidity properties of frameworks correspond to matroid representations, where the independent sets are those yielding full-rank submatrices of the rigidity matrix for generic placements.^[84]

Discrete Differential Geometry

Discrete differential geometry develops discrete analogs of concepts from smooth differential geometry, particularly for triangulated surfaces represented as triangle meshes, where vertices, edges, and faces approximate a continuous surface. These meshes provide a combinatorial structure that preserves key geometric properties, such as local flatness and global topology, enabling computational treatment of curvature and other invariants. A fundamental notion is the discrete Gaussian curvature at a mesh vertex v_i, defined as the angle defect: the deviation of the sum of incident face angles from $2\pi. Specifically, if \theta_{ij} denotes the angle at v_i in the j-th adjacent triangle, then the discrete Gaussian curvature is given by

K_i = 2\pi - \sum_j \theta_{ij}.

This measure captures local bending, with positive values indicating convex regions and negative values concave ones, and integrates to $2\pi \chi(M) over the mesh via a discrete Gauss-Bonnet theorem, where \chi(M) is the Euler characteristic.^[89]^[90] The discrete Laplacian operator on meshes, essential for tasks like smoothing, is often formulated using cotangent weights to mimic the smooth Laplace-Beltrami operator. For a function f on vertices, the cotangent Laplacian at vertex v_i with Voronoi area A_i is

\Delta f(v_i) = \frac{1}{2A_i} \sum_{j \sim i} (\cot \alpha_{ij} + \cot \beta_{ij}) (f_j - f_i),

where \alpha_{ij} and \beta_{ij} are the angles opposite the edge v_i v_j in adjacent triangles. This operator is positive semi-definite and rotationally invariant, making it suitable for mesh smoothing via heat diffusion or optimization, as it averages values weighted by edge lengths and angles.^[90]^[91] Integrable discretizations extend these ideas by preserving underlying symmetries, such as those from the smooth theory's integrable systems. Discrete minimal surfaces, for instance, are constructed via parallel meshes or curvature-line parametrizations that satisfy a discrete zero-mean-curvature condition, allowing iterative computation from boundary data while maintaining conjugate or associate surface families. Similarly, the discrete Willmore energy, \sum_i (H_i^2 - K_i) A_i where H_i approximates mean curvature, drives flows toward surfaces of low bending energy, with minimizers converging to smooth Willmore surfaces under refinement.^[92]^[93] Key theorems establish the validity of these discretizations: under successive refinement (e.g., midpoint subdivision), the discrete Gaussian and mean curvatures converge to their smooth counterparts for sufficiently regular meshes approaching a C^2 surface, with error rates depending on mesh quality. Post-2020 advances in discrete Ricci flow have enhanced conformal mapping of meshes, evolving edge lengths to prescribe target curvatures via a discrete Yamabe flow, enabling robust parameterization of high-genus surfaces with bounded distortion.^[94]^[95]^[96] Circle packings exemplify discrete conformal structures, where tangent circles at vertices encode a metric with prescribed intersection angles, realizing Thurston's conjecture that such packings exist and are unique up to Möbius transformations for simply connected domains, as proved by Rodin and Sullivan, providing a combinatorial analog to the Riemann mapping theorem. These tools find application in digital models for animation and simulation.^[97]

Computational and Applied Topics

Digital Geometry

Digital geometry examines the geometric properties of subsets within digital pictures, which are represented as finite arrays of points or cells on the integer lattice \mathbb{Z}^d, where d=2 for 2D images (pixels) and d=3 for 3D images (voxels).^[98] These grids model discrete approximations of continuous objects, enabling the derivation of shapes, distances, and topological features from raster data in image processing.^[98] Pioneered by Azriel Rosenfeld in the 1960s and 1970s, the field bridges discrete structures with Euclidean geometry, focusing on algorithms that preserve essential properties like connectivity and convexity.^[98] A key topological foundation is the digital analog of the Jordan curve theorem, which addresses how simple closed pixel chains divide the digital plane. Khalimsky's theorem, for instance, states that in the Khalimsky topology on \mathbb{Z}^2, the complement of a Jordan curve consists of two path-connected components: an interior and an exterior.^[99] In 3D, connectivity paradoxes—such as a single object appearing disconnected or a simply connected background becoming multiply connected—arise from inconsistent adjacency definitions; these are resolved using 26-connectivity for objects (considering all 26 neighboring voxels) paired with 6-connectivity for the background (face-adjacent only), ensuring topological consistency analogous to continuous space.^[100] Distance metrics are essential for quantifying separations in digital spaces. The city-block distance, based on the L1 norm, sums absolute differences in coordinates and produces diamond-shaped balls, but it poorly approximates the Euclidean metric with higher directional bias.^[101] Chamfer distances improve this by using weighted local masks (e.g., in 3×3 neighborhoods with weights approximating \sqrt{2}) to propagate integer distances that form near-circular balls, achieving mean absolute errors as low as 3.96% relative to Euclidean distances.^[101] Rosenfeld's criteria for digital convexity provide a discrete counterpart to continuous convexity. A finite set S \subset \mathbb{Z}^2 is digitally convex if, for any two points P, Q \in S, the digital line segment joining them is entirely contained in S; equivalently, no three collinear points in S have the middle point outside S, and every point on the real line segment PQ is within city-block distance 1 of some point in S.^[102] This ensures S is the digitization of a convex Euclidean set, facilitating applications like shape recognition.^[102] Thinning and skeletonization algorithms extract one-pixel-wide representations of digital shapes while preserving topology. These methods iteratively delete simple border points (those whose removal does not alter connectivity) until a thin skeleton remains, often guided by distance transforms to ensure mediality.^[103] For example, distance-ordered homotopic thinning processes voxels in ascending order of their chamfer distance to the background, maintaining homotopy and producing reversible skeletons suitable for 3D shape analysis.^[103] Representative algorithms include Bresenham's line drawing method, which rasterizes a line between grid points by minimizing an incremental error term, selecting pixels that best approximate the continuous line using only integer arithmetic. Digital convex hulls extend this to boundaries: for a digital region, the DL-convex hull is the smallest DL-convex set containing it, where DL-convexity requires that digital straight lines between any pair of pixels lie fully within the set; computation involves iterative boundary adjustments to enclose the region.^[104]

Algorithms and Optimization

Discrete geometry encompasses a range of computational challenges where efficient algorithms are essential for processing geometric structures such as point sets, polytopes, and arrangements. Key algorithms address fundamental problems like convex hull computation, which determines the smallest convex set containing a given set of points. The Jarvis march, also known as the gift-wrapping algorithm, computes the convex hull in O(nh) time, where n is the number of points and h is the number of hull vertices, by iteratively selecting the next hull point as the one forming the smallest polar angle with the previous edge. This method, introduced by Jarvis in 1973, is particularly effective when h is small relative to n. In contrast, the Graham scan achieves O(n log n) time complexity by first sorting points by polar angle around a reference point and then performing a linear scan to eliminate non-hull points, making it suitable for general cases.^[105] Optimization in discrete geometry often involves formulating problems as integer linear programs (ILPs) to handle constraints like non-overlapping placements in packing scenarios. For geometric packing, ILPs model decisions on item orientations and positions, minimizing space usage subject to intersection-free conditions; for instance, mixed-integer programming formulations have been developed for three-dimensional irregular strip packing, incorporating binary variables for rotation choices and continuous variables for coordinates.^[106] Branch-and-bound techniques are employed for tiling problems, where the search tree branches on tile placements and bounds prune infeasible or suboptimal subproblems, as demonstrated in models for tiling finite regions with polyominoes.^[107] These methods leverage relaxation bounds to explore the discrete solution space efficiently. Many optimization problems in discrete geometry exhibit high computational complexity, with three-dimensional bin packing proven to be strongly NP-hard due to its generalization of the one-dimensional bin packing problem and the intractability of exact solutions for heterogeneous item sets.^[108] To address this, approximation algorithms provide near-optimal solutions in polynomial time; for bin packing, polynomial-time approximation schemes (PTAS) exist that achieve (1 + ε)-approximation for any ε > 0, by grouping items into size classes and solving subinstances optimally via dynamic programming.^[109] Covering problems, such as selecting minimal sets of geometric objects to cover a space, can be formulated as set cover ILPs:

\begin{align*} \min &\quad \sum_i c_i x_i \\ \text{s.t.} &\quad \sum_{i: e \in S_i} x_i \geq 1 \quad \forall e \\ &\quad x_i \in \{0,1\} \quad \forall i \end{align*}

where S_i are subsets covering elements e, and this arises in discrete settings like line covers for point sets.^[110] Software libraries facilitate implementation of these algorithms and optimizations in discrete geometry. The CGAL (Computational Geometry Algorithms Library) provides robust support for computing arrangements of curves and surfaces, enabling exact constructions of planar and spatial subdivisions used in optimization pipelines.^[111] Similarly, the LEDA library offers data structures and algorithms for geometric graphs, including representations of planar maps and shortest paths, which underpin tiling and packing computations. Post-2020 advancements integrate machine learning for heuristic optimization, particularly generative adversarial networks (GANs) to approximate solutions for complex tilings. SeamlessGAN, for example, synthesizes tileable texture maps by training on single inputs to produce non-overlapping, periodic patterns, serving as a heuristic for aperiodic or quasi-periodic tiling designs in discrete geometric modeling.^[112]

Applications in Computer Science and Beyond

Discrete geometry plays a pivotal role in computer graphics, particularly in mesh generation and collision detection. In mesh generation, discrete geometric structures such as triangulations and simplicial complexes are used to approximate continuous surfaces for rendering 3D models, enabling efficient computation of surface properties like curvature and normals. For instance, Delaunay triangulations facilitate adaptive mesh refinement in finite element simulations integrated into graphics pipelines. Collision detection relies on bounding volumes derived from discrete geometric hierarchies, such as oriented bounding boxes or k-d trees built from point sets, to accelerate real-time interactions in simulations and games by reducing pairwise checks from O(n²) to near-linear time in practice. In robotics, discrete geometry underpins motion planning through configuration spaces represented as visibility graphs or roadmaps. Visibility graphs, constructed from discrete polygonal obstacles, connect vertices to form shortest paths that avoid collisions, a method foundational to algorithms like the visibility graph search used in autonomous navigation. These graphs discretize the continuous configuration space into a combinatorial structure, allowing planners to find feasible trajectories for robots with multiple degrees of freedom, as demonstrated in industrial arm manipulators and mobile robots. Applications in artificial intelligence and machine learning leverage discrete geometry for processing 3D data and analyzing complex datasets. In 3D vision, point cloud processing employs discrete geometric primitives like nearest-neighbor graphs and Voronoi diagrams to segment and reconstruct scenes from sensor data, enhancing tasks such as object detection in autonomous vehicles. Topological data analysis (TDA), rooted in discrete simplicial complexes, extracts persistent features from high-dimensional datasets via tools like Mapper or persistence diagrams, revealing underlying structures in noisy data for applications in anomaly detection and clustering. Beyond computer science, discrete geometry informs diverse fields including crystallography, architecture, and biology. In crystallography, lattice modeling uses discrete point lattices and symmetry groups to predict crystal structures, with Voronoi tessellations aiding in the analysis of atomic packings observed in X-ray diffraction patterns. Architectural designs incorporate discrete tilings and polyhedral approximations for facades and space-filling patterns, as seen in parametric modeling of geodesic domes that optimize material use through combinatorial geometry. In biology, rigidity theory from discrete geometry models protein folding by treating structures as bar-joint frameworks, assessing flexibility to understand enzymatic functions and drug binding sites. Post-2020 advancements highlight discrete geometry's role in emerging technologies. Simulations of discrete groups in quantum computing utilize finite geometric lattices to model qubit interactions and error correction codes, enabling scalable algorithms for quantum error mitigation as explored in lattice-based quantum walks. In logistics, AI-driven discrete optimization employs geometric graph partitioning and facility location problems on discrete spaces to route vehicles efficiently, reducing fuel consumption in urban delivery networks through metaheuristic approaches grounded in combinatorial geometry. Specific examples illustrate broader impacts, such as GPS signal processing, where geometric graphs from discrete Delaunay triangulations enhance positioning accuracy by modeling multipath interference in urban environments. In virtual reality rendering, simplicial complexes discretize dynamic scenes for real-time topological updates, supporting immersive interactions with minimal latency in headset displays. Digital image analysis briefly benefits from these techniques in edge detection via discrete curvature estimation.

References

[1]
[PDF] math 149, fall 2013 discrete geometry lecture notes
Discrete Geometry is the study of arrangements of discrete sets of objects in space. The goal of this course is to give an introduction to some of the classical ...
[2]
[PDF] Lectures on Discrete and Polyhedral Geometry - UCLA Mathematics
Apr 20, 2010 · The lectures cover basic discrete geometry, including the Helly theorem, and discrete geometry of curves and surfaces, such as the four vertex ...
[3]
[PDF] An introduction to convex and discrete geometry Lecture Notes
These lecture notes cover an introduction to convex and discrete geometry, including Euclidean space, convex hulls, and separation theorems.
[4]
[PDF] Discrete Geometry and Geometric Graph Theory
Overview: Discrete geometry has become an important are of mathemat- ics with applications to computer graphics, modelling, brain imaging, and many other ...
[5]
[PDF] Convex and Discrete Geometry: Ideas, Problems and Results
Convex geometry is an area of mathematics between geometry, analysis and discrete mathema- tics. Classical discrete geometry is a close relative of convex ...
[6]
[PDF] Introduction to Discrete Geometry
Linear subspaces. Let Rd denote the d-dimensional Euclidean space. The points are d-tuples of real numbers, x = (x1,x2,...,xd).
[7]
Combinatorics and Discrete Geometry | Department of Mathematics
Discrete geometry is concerned with properties of finitely generated geometric objects such as polytopes and polyhedra, triangulations and polyhedral complexes ...Missing: definition | Show results with:definition
[8]
Mathematisches Forschungsinstitut Oberwolfach Discrete Geometry
Discrete Geometry deals with the structure and complexity of discrete geometric objects ranging from finite point sets in the plane to more complex ...
[9]
None
### Key Points on Discrete vs. Continuous Mathematics in Relation to Geometry
[10]
[PDF] Geometric Modeling Based on Polygonal Meshes
Representing a given (real or virtual) surface geometry by a polygonal mesh is usually an approximation process. Hence there is no unique polygonal 3D–model but ...
[11]
[1009.2292] A discrete Gauss-Bonnet type theorem - arXiv
Sep 13, 2010 · For many abstract two dimensional graphs, the sum over all K curvatures is 60 times the Euler characteristic. Under which conditions this ...
[12]
[PDF] (Discrete) Differential Geometry
• Normal curvature = curvature of the normal curve at point point. • Can be ... • “Discrete Differential-Geometry Operators for Triangulated 2-.
[13]
(PDF) What lies between rigidity and flexibility of structures
Aug 9, 2025 · The borderline between continuous flexibility and rigidity of structures like polyhedra or frameworks is not strict.
[14]
A Literature Review on Circle and Sphere Packing Problems ...
Jul 5, 2009 · Obviously, packing circular objects gives rise to optimization problems, but their classification into continuous or discrete problems is fuzzy.<|control11|><|separator|>
[15]
The Geometrical Work - of Girard Desargues
The Rough Draft on Conics (1639). The original title of Desargues' work is Brouillon proiect d'une atteinte aux evenemens des rencontres du Cone avec un Plan ...
[16]
[PDF] HANDBOOK OF CONVEX GEOMETRY - UC Davis Math
[CAUCHY 1813]: Two convex polyhedra comprised of the same number of equal similarly placed faces are superposable or symmetric. Cauchy's Theorem was the ...Missing: history | Show results with:history<|separator|>
[17]
The four colour theorem - MacTutor History of Mathematics
The Four Colour Conjecture first seems to have been made by Francis Guthrie. He was a student at University College London where he studied under De Morgan.
[18]
[PDF] revisiting the hexagonal lattice: on optimal lattice circle packing
The first claim of a proof was made by Axel Thue in 1892, and then once again in 1910. ... Well-rounded lattices are very important in coding theory [1] and.
[19]
[PDF] Combinatorial Aspects of Convex Polytopes - Margaret Bayer
Aug 1, 1991 · A convex polyhedron is a subset of d that is the intersection of a finite number of closed halfspaces. A bounded convex polyhedron is called a ...
[20]
[PDF] CONVEX POLYTOPES
Introduction. The study of convex polytopes in Euclidean space of two and three dimensions is one of the oldest branches of mathematics.
[21]
Polyhedral Formula -- from Wolfram MathWorld
A formula relating the number of polyhedron vertices V, faces F, and polyhedron edges E of a simply connected (i.e., genus 0) polyhedron (or polygon).<|separator|>
[22]
Platonic Solid -- from Wolfram MathWorld
The Platonic solids, also called the regular solids or regular polyhedra, are convex polyhedra with equivalent faces composed of congruent convex regular ...
[23]
Archimedean Solid -- from Wolfram MathWorld
In the table, 'P' denotes Platonic solid, 'M' denotes a prism or antiprism, 'A' denotes an Archimedean solid, and 'T' a plane tessellation. fg.
[24]
Schläfli Symbol -- from Wolfram MathWorld
A symbol of the form {p,q,r,...} used to describe regular polygons, polyhedra, and their higher-dimensional counterparts.
[25]
f-vector - PlanetMath.org
Mar 22, 2013 · Let P be a polytope of dimension d. The f-vector of P is the finite integer sequence (f0,…, fd−i) , f d - i ) , where the component.
[26]
Joseph Malkevitch: Steinitz's Theorem and Mani's Theorem - CUNY
A graph G is 3-polytopal, that is, the vertex-edge graph of a 3-dimensional convex polyhedron if and only if G is planar and 3-connected. Steinitz's Theorem ...
[27]
Tesseract -- from Wolfram MathWorld
The tesseract is the hypercube in R^4, also called the 8-cell or octachoron. It has the Schläfli symbol {4,3,3}, and vertices (+/-1,+/-1,+/-1,+/-1).
[28]
Packing, covering and tiling in two-dimensional spaces
Packing, covering and tiling is a fascinating subject in pure mathematics. It mainly deals with arrangement patterns and efficiencies of geometric objects.
[29]
A proof of the Kepler conjecture - Annals of Mathematics
A proof of the Kepler conjecture. Pages 1065-1185 from Volume 162 (2005), Issue 3 by Thomas C. Hales. Abstract: No abstract available for this article.
[30]
A FORMAL PROOF OF THE KEPLER CONJECTURE
May 29, 2017 · This article describes a formal proof of the Kepler conjecture on dense sphere packings in a combination of the HOL Light and Isabelle proof assistants.
[31]
[1009.4322] A Simple Proof of Thue's Theorem on Circle Packing
A simple proof of Thue theorem on Circle Packing is given. The proof is only based on density analysis of Delaunay triangulation for the set of points that are ...Missing: 1892 discrete
[32]
[PDF] Some packing and covering theorems.
Fejes Tóth: Packing an covering theorems. 63-. Theorem 2. If N is the number of certain congruent convex domains covering a hexagon. fj' in such a way that ...Missing: original | Show results with:original
[33]
On a conjecture of L. Fejes Tóth and J. Molnár about circle coverings ...
Oct 13, 2018 · Tóth and Molnár (Math Nachr 18:235–243, 1958) formulated the conjecture that for a given homogeneity q the thinnest covering of the Euclide.
[34]
[PDF] J - NYU Courant Mathematics
J "$ % '(. Summary A geometric graph is a graph drawn in the plane such that its vertices are points in general position and its edges are straight-line ...
[35]
(PDF) Fáry's Theorem for 1-Planar Graphs - ResearchGate
Aug 7, 2025 · Fáry's theorem states that every plane graph can be drawn as a straight-line drawing. A plane graph is a graph embedded in a plane without ...
[36]
[PDF] Kuratowski's Theorem - UChicago Math
Aug 28, 2017 · This paper introduces basic concepts and theorems in graph the- ory, with a focus on planar graphs. On the foundation of the basics, we state.Missing: geometric Fáry's
[37]
The crossing number inequality | What's new - Terry Tao
Sep 18, 2007 · This inequality gives a useful bound on how far a given graph is from being planar, and has a number of applications, for instance to sum-product estimates.
[38]
[math/9910185] Geometric Thickness of Complete Graphs - arXiv
Nov 1, 1999 · We define the geometric thickness of a graph to be the smallest number of layers such that we can draw the graph in the plane with straight-line edges.
[39]
[PDF] The Geometric Thickness of Low Degree Graphs
Dec 11, 2003 · We will show that graphs of maximum degree three have geometric thickness two in two steps: (1) decomposing the graph into two subgraphs and (2) ...
[40]
[PDF] Geometric Graphs: Theory and Applications - NII Shonan Meeting
For example, map labeling, problems in wireless and sensor networks and VLSI physical design, database queries, etc. Here the vertices of the graph are mapped.
[41]
(PDF) Graphs in VLSI circuits and systems - ResearchGate
Mar 14, 2024 · A graph is an effective tool for managing the complexity of large scale VLSI systems. By reducing the complex components of a VLSI system into nodes and edges.
[42]
[PDF] Geometry of Arrangements that Determine Shapes - arXiv
Dec 14, 2020 · A finite geometry is a point-line incidence structure that satisfies certain additional rules. The rules that such an incidence structure ...
[43]
[PDF] FinInG: a package for Finite Incidence Geometry - arXiv
Jun 16, 2016 · All geometries that can be constructed in FinInG are incidence structures. This terminology is consistently used, as illustrated in Example 3.1 ...
[44]
[PDF] Existence of Projective Planes - arXiv
Mar 17, 2016 · The strongest proof of existence was that projective planes of order n exist whenever n is a prime power i.e. for any n = pq, where p is ...
[45]
[PDF] Incidence geometry of the Fano plane and Freudenthal's ansatz for ...
Mar 7, 2022 · In this article we consider structures on a Fano plane F which allow a generalisation of Freudenthal's construction of a norm and a bilinear ...
[46]
[PDF] A constructive approach to affine and projective planes - arXiv
Jan 19, 2016 · We start by constructing projective and affine planes over local rings and establishing forms of Desargues' Theorem and Pappus' Theorem which ...<|separator|>
[47]
[PDF] Incidence Bounds for Block Designs
Abstract. We prove three theorems giving extremal bounds on the incidence structures determined by subsets of the points and blocks of a balanced incomplete ...
[48]
[PDF] arXiv:1206.1107v2 [math.CO] 21 Oct 2012
Oct 21, 2012 · [5] R. H. Bruck and H. J. Ryser. The nonexistence of certain finite projective planes. Canadian J. Math., 1:88–93, 1949.
[49]
[PDF] Design of Ciphers based on the Geometric Structure of the Möbius ...
Feb 20, 2021 · Definition 6.1. An incidence structure (S,X) with a set of points S and a set of circles X is called Möbius plane, if it satisfies following ...
[50]
[PDF] arXiv:2011.10700v2 [math.GM] 10 Oct 2024
Oct 10, 2024 · An arrangement (L, P) has lines L and points P, where any point in P is intersection of at least two lines in L, and nonparallel lines in L ...
[51]
[PDF] 6 ORIENTED MATROIDS - CSUN
INTRODUCTION. The theory of oriented matroids provides a broad setting in which to model, de- scribe, and analyze combinatorial properties of geometric ...Missing: seminal | Show results with:seminal
[52]
[PDF] ORIENTED MATROIDS - science-to-touch
7.2.1 COVECTOR AXIOMS. DEFINITION (Covector Axioms): An oriented matroid given in terms of its covectors is a pair M := (E, L), where L ∈ {−, 0, +}E ...
[53]
[PDF] Oriented Matroids Today - The Electronic Journal of Combinatorics
Apr 15, 2024 · Oriented matroids model geometric situations, generalizing objects like point and vector configurations, and hyperplane arrangements.
[54]
[PDF] ORIENTED MATROIDS - Jürgen Richter-Gebert and Günter M. Ziegler
Oriented matroids model geometric configurations, extracting relative position and orientation. They are matroids where each basis has an orientation, encoding ...
[55]
[PDF] 3 Simplicial Complexes - Stanford Computer Graphics Laboratory
Definition 3.9 (abstract simplicial complex) An abstract simplicial complex is a set S of finite sets such that if A ∈ S, so is every subset of A. We say A ∈ S ...
[56]
[PDF] Two Complexes Which are Homeomorphic But Combinatorially ...
Two Complexes Which are Homeomorphic But Combinatorially Distinct. Author(s): John Milnor. Source: Annals of Mathematics , Nov., 1961, Second Series, Vol. 74 ...
[57]
[PDF] A Brief Glimpse of Topological Combinatorics
May 5, 2015 · This survey seeks to give a brief glimpse of such beautiful topic of topological combinatorics. We survey three kinds of combinatorial problems.Missing: paper | Show results with:paper
[58]
https://graphics.stanford.edu/courses/cs164-09-spring/Protected/afra_lectures2.pdf
[59]
Kneser's conjecture, chromatic number, and homotopy - ScienceDirect
View PDF; Download full issue. Search ScienceDirect. Elsevier · Journal of Combinatorial Theory, Series A · Volume 25, Issue 3, November 1978, Pages 319-324.
[60]
[PDF] Homology and Shellability of Matroids and Geometric Lattices
Shellability was established for matroid and broken circuit complexes by Provan (1977) and for order complexes of geometric lattices by Björner (1980a).Missing: citation | Show results with:citation
[61]
[math/0405393] On the Topological Tverberg Theorem - arXiv
May 20, 2004 · Title:On the Topological Tverberg Theorem ; Comments: 45 pages, 13 figures, 3 tables ; Subjects: Combinatorics (math.CO); Algebraic Topology (math ...
[62]
Point-Level Topological Representation Learning on Point Clouds
Jun 4, 2024 · This paper proposes a method to extract node-level topological features from point clouds using discrete variants of algebraic topology and ...
[63]
[PDF] 14 The geometry of numbers - 14.1 Lattices in real vector spaces
Oct 27, 2021 · Definition 14.4. A (full) lattice in V ≃ Rn is a Z-submodule generated by an R-basis, equivalently, a discrete cocompact subgroup.
[64]
[PDF] Lattices - Universiteit Leiden
1. Introduction. A lattice is a discrete subgroup of a Euclidean vector space, and geometry of numbers is the theory that occupies itself with lattices.
[65]
[PDF] Lattices Michel Waldschmidt - IMJ-PRG
Jul 22, 2025 · First definition of a lattice: A lattice is a discrete subgroup of maximal rank in an Euclidean vector space. Hence the rank of a lattice in an ...
[66]
[PDF] Minkowski's successive minima in convex and discrete ge
May 17, 2023 · Abstract. In this short survey we want to present some of the impact of Minkowski's successive minima within Convex and Discrete Geometry.
[67]
On extensions of Minkowski's theorem on successive minima - arXiv
May 20, 2014 · Minkowski's 2nd theorem in the Geometry of Numbers provides optimal upper and lower bounds for the volume of a o-symmetric convex body in terms ...
[68]
[PDF] Fuchsian Groups: Intro - UCSD Math
A Fuchsian group is a discrete subgroup of PSL(2, R) that acts properly discontinuously on the upper half plane.
[69]
[PDF] hyperbolic geometry, fuchsian groups, and tiling spaces
Fuchsian groups are character- ized, and applied to construct tilings of hyperbolic space.
[70]
[PDF] Crystallographic Groups
Crystallographic groups deal with the structure of crystals, which are often described by their periodic nature.
[71]
[PDF] Periodicity, Quasiperiodicity, and Bieberbach's Theorem on ... - People
A czystallographic group is a discrete, cocompact group of isometries of n- dimensional Euclidean space. All terms in this definition are explained in Section.
[72]
[1512.00720] Voronoi Cells of Lattices with Respect to Arbitrary Norms
Nov 27, 2015 · We study the geometry and complexity of Voronoi cells of lattices with respect to arbitrary norms.
[73]
Voronoi Cells of Lattices with Respect to Arbitrary Norms - SIAM.org
We study the geometry and complexity of Voronoi cells of lattices with respect to arbitrary norms. On the positive side, we show for strictly convex and ...
[74]
n-dimensional Delaunay Triangulation of Lattices - MathOverflow
Oct 31, 2013 · But perturbing the coordinates of the basis further, and generically, will produce a true Delaunay triangulation with the same properties).Uniqueness constraints for Delaunay triangulation - MathOverflowOptimal triangulation of points distributed on two parallel linesMore results from mathoverflow.net
[75]
[PDF] Lecture 16 — Root Systems and Root Lattices
Nov 1, 2010 · Note that an even lattice is always integral: if α,β ∈ Q, Q even, then. (α + β,α + β)=(α,α)+(β,β) + 2(α,β), (α,α),(β,β) ∈ 2Z. Hence 2(α,β) ∈ 2Z, ...
[76]
[PDF] Lattices - Andries E. Brouwer
Jan 17, 2002 · The examples. The irreducible root lattices one finds are An (n ≥ 0), Dn (n ≥ 4), E6, E7,. E8. Each is defined by its Dynkin diagram. 5. Page 6 ...
[77]
The rigidity of graphs - Semantic Scholar
Nov 1, 1978 · Math. 2022. We develop a rigidity theory for bar-joint frameworks in Euclidean $d$-space in which specified ...
[78]
[PDF] Rigidity of graphs
Feb 25, 2011 · Theorem (Asimow, Roth 1979). For generic p,. (G,p) is rigid ⇔ rankR(G,p) = d|V | − d(d + 1)/2. Page 17. Determining rigidity. Preliminaries.
[79]
[PDF] On graphs and rigidity of plane skeletal structures
This paper investigates the combinatorial properties of rigid plane skeletal structures, which are described by a class of graphs. A plane skeletal structure ...
[80]
[PDF] Combinatorics and the rigidity of frameworks - WPI
(8) [Graver [14]] A2 is maximal among all 2-dimensional abstract rigidity ma- troids. Laman's Theorem was proved in 1970 and it was this theorem that promoted ...
[81]
[PDF] CHARACTERIZING GENERIC GLOBAL RIGIDITY - Computer Science
Theorem 1.6 (Asimow-Roth [1]). If a generic framework ρ ∈ Cd(Γ) of a graph Γ with d+1 or more vertices is locally rigid in Ed, then it is infinitesimally rigid.
[82]
[PDF] Reciprocal Figures for determining forces in framed structures
About 1864, the increasing use of framed structures, such as bridges and roof trusses, designers adopted graphical methods for determining the forces in ...
[83]
[PDF] Cauchy's Theorem and Edge Lengths of Convex Polyhedra
Cauchy proved that convex polyhedra are rigid in the sense that if the faces were metal plates, and the edges were hinges, no flexing would be possible.Missing: history | Show results with:history
[84]
[PDF] REMARKS ON BRICARD'S FLEXIBLE OCTAHEDRA OF TYPE 3
This paper treats exible polyhedra in the Eu lidean 3- spa e. It is shown how the exibility of Bri ard's o ta- hedra of Type 3 an be on luded with the aid of ...
[85]
[PDF] DISCRETE DIFFERENTIAL GEOMETRY - Keenan Crane
The angle defect at a vertex i is the deviation of the sum of interior angles from the Euclidean angle sum of 2π: Intuition: how “flat” is the vertex? Page 12 ...Missing: meshes | Show results with:meshes
[86]
[PDF] Discrete Differential-Geometry Operators for Triangulated 2-Manifolds
In this paper we define and derive the first and second order differential attributes (normal vector n, mean curvature κH, Gaussian curvature κG, principal ...Missing: defect | Show results with:defect
[87]
[PDF] Laplacian Mesh Processing - People @EECS
The spatial Lapla- cian operator ∆, restricted to the mesh, is discretized using the cotangent weights. By inspecting Eq. (6), we can see that it has a similar ...
[88]
[PDF] Computing Discrete Minimal Surfaces and Their Conjugates
Abstract. We present a new algorithm to compute stable discrete minimal surfaces bounded by a number of fixed or free boundary curves in R3, S3 and H3.
[89]
[PDF] Discrete Willmore Flow
Abstract. The Willmore energy of a surface, ∫ (H2 − K)dA, as a function of mean and Gaussian curvature, captures the deviation of a surface from (local) ...
[90]
Discrete schemes for Gaussian curvature and their convergence
The popular angular defect schemes for Gaussian curvature only converge at the regular vertex with valence 6. In this paper, we present a new discrete ...
[91]
[PDF] Lectures in Discrete Differential Geometry 3 – Discrete Surfaces
Mar 19, 2014 · Gaussian curvature – we will verify shortly that the angle-deficit formula for discrete Gaussian curvature has a discrete Gauss-Bonnet theorem.Missing: defect | Show results with:defect
[92]
High genus surface parameterization using the Euclidean Ricci flow ...
May 22, 2025 · For each triangle in the mesh, we calculate the angles before and after the conformal mapping. And angle distortion measures how much the angles are distorted ...
[93]
[PDF] The Approximation of Conformal Structures via Circle Packing
Thurston conjectured and Rodin and Sullivan proved that the discrete conformal maps fn converge uniformly on compact subsets of D to the classical conformal ...
[94]
(PDF) Digital Geometry - ResearchGate
Feb 14, 2015 · Digital geometry is about deriving geometric information from digital pictures. The field emerged from its mathematical roots some ...
[95]
[PDF] Digital Jordan Curve Theorems | Semantic Scholar
A new, short proof of Khalimsky's digital Jordan curve theorem is presented using induction on the Euclidean length of the curve to prove that the theorem ...Missing: chains | Show results with:chains
[96]
[PDF] Axiomatic Digital Topology - arXiv
Even the few consistent pairs, (4, 8) and (8, 4) in 2D and (6, 26) and (26, 6) in. 3D, have important drawbacks: a) They are only applicable in cases when ...
[97]
[PDF] Optimum Design Of Chamfer Distance Transforms - CVSP - NTUA
Chamfer distance transforms are a class of discrete algorithms that offer a good approximation to the desired. Euclidean distance transform at a lower ...
[98]
None
### Rosenfeld's Criteria for Digital Convexity
[99]
Distance-Ordered Homotopic Thinning: A Skeletonization Algorithm ...
Distance-ordered homotopic thinning (DOHT) is a technique for skeletonizing 3D images, producing homotopic, thin, and medial skeletons by deleting points in ...
[100]
ON THE COMPUTATION OF THE DIGITAL CONVEX HULL AND ...
A region is DL-convex if, for any two pixels belonging to it, there exists a digital straight line between them all of whose pixels belong to the region. DL- ...
[101]
[PDF] an efficient algorith for determining the convex hull of a finite planar set
In this note we describe an algorithm which determines CH(S) in no more than (n log n)/. (log 2) + cn "operations" where c is a small positive constant which ...
[102]
Mixed-integer linear programming models for 3D irregular strip ...
Oct 31, 2025 · This paper addresses this gap in the literature by formulating and solving exact models of three-dimensional irregular strip packing problems.
[103]
[PDF] a new mathematical model for tiling finite regions of the plane with ...
These optimization packages carry out the optimization process by branch-and-bound algorithms, including some general purpose heuristics. For a survey of modern ...
[104]
The Three-Dimensional Bin Packing Problem | Operations Research
The problem is strongly NP-hard and extremely difficult to solve in practice. Lower bounds are discussed, and it is proved that the asymptotic worst-case ...
[105]
[PDF] PTAS for Bin-Packing
Nov 29, 2010 · Step 1. Sort the subsets by the sum of their sizes. Those with sum not exceeding 1 can be packed in a single bin. Call them 1-bin subsets.
[106]
[PDF] Covering Geometric Sets with Lines - EuroCG 2024
Mar 15, 2024 · Different methods for efficiently computing a discrete set of candidate lines that limit the size of the ensuing set cover instance. Exact ...
[107]
CGAL 6.1 - 2D Arrangements: User Manual
This package provides a data structure that represents a two-dimensional arrangement of curves embedded in an orientable parametric surface in three dimensional ...
[108]
[PDF] SeamlessGAN: Self-Supervised Synthesis of Tileable Texture Maps
SeamlessGAN automatically generates tileable texture maps from a single input, using a deep generative model to create seamless single-tiles.