# Discrete geometry Discrete geometry studies the [[Combinatorics|combinatorial]] behavior of finitely many geometric objects — point sets, lines, spheres, [[Polytope|polytopes]], tilings, lattices — asking not for measure but for count, incidence, and arrangement. Its signature problems are easy to state and brutally hard to close: how densely can equal spheres pack (Kepler, 1611; settled by Hales, 1998, and formally verified in 2014); can a single tile be forced to cover the plane without ever repeating (yes — [[Penrose_tiling|Penrose's]] pair in 1974, a lone "hat" in 2023); how many incidences can n points and n lines share. Its results flow directly into working systems: lattice packings *are* the codebooks of [[Error_detection_and_correction]], LLL-reduced lattices power post-quantum [[Cryptography]], [[Tessellation|tessellations]] model [[Quasicrystal|quasicrystals]], and the whole subject supplies [[Computational_geometry]] with the combinatorial bounds its [[Algorithm|algorithms]] must respect. ## Packing spheres, from Kepler to E₈ Kepler asserted (1611) that no packing of equal spheres beats the grocer's pyramid at density π/√18 ≈ 0.7405. The plane's version — hexagonal circles at π/√12 ≈ 0.9069 — was settled rigorously by Fejes Tóth (1942); Kepler's own claim resisted until Hales's computer-assisted proof (1998), whose scale provoked the Flyspeck project (completed 2014) to re-verify every step in a proof assistant, a milestone for machine-checked [[Correctness_(computer_science)|correctness]] in [[Mathematics]]. Then dimension went strange and beautiful: Viazovska (2016) proved the E₈ lattice optimal in dimension 8 with an explicit magic function built by [[Fourier_analysis]], and the method closed dimension 24 (Leech lattice) within months — a Fields Medal in 2022. Kissing numbers echo the story: 12 in three dimensions (a dispute of [[Isaac_Newton|Newton's]], settled 1953), 240 for E₈, 196,560 for Leech. Physical matter votes too: face-centered [[Cubic_crystal_system|cubic]] crystals realize Kepler density, and hard spheres in [[Molecular_dynamics]] simulations crystallize spontaneously under pressure (Alder–Wainwright, 1957) — a purely entropic [[Phase_transition]], with disordered "random close packing" jamming near 0.64. ## Tilings, undecidability, and forced aperiodicity Which shapes tile the plane, and how? The periodic answers were classified early — exactly 17 wallpaper [[Group_theory|symmetry groups]] (Fedorov, 1891) — but the deeper surprise came from [[Logic]]: Berger (1966) proved the domino problem undecidable, meaning no [[Algorithm]] decides whether an arbitrary tile set tiles the plane, and undecidability requires the existence of *aperiodic* tile sets — sets that tile only nonperiodically, computation's shadow falling on [[Geometry]] via the [[Theory_of_computation]]. Penrose cut the count to two tiles (1974), whose five-fold [[Penrose_tiling|quasiperiodic patterns]] were then found in nature when Shechtman's 1982 diffraction images revealed [[Quasicrystal|quasicrystals]] — long-range order, sharp diffraction peaks, no periodicity, a Nobel Prize in 2011. The 2023 "hat" and its chiral cousin closed the oldest gap: a single tile, an einstein, that admits only aperiodic [[Tessellation|tessellations]]. Aperiodic order sits at the boundary of [[Self-organization]]: local matching rules, global pattern, zero repetition. ## Polytopes and their combinatorial skeletons A [[Polytope]] is the convex hull of finitely many points; its faces form a lattice that pure [[Combinatorics]] can interrogate. Euler's relation V − E + F = 2 (1752) starts the census; Steinitz (1922) characterized exactly which [[Graph_theory|graphs]] are skeletons of 3-dimensional [[Polyhedron|polyhedra]] — the planar 3-connected ones; McMullen's Upper Bound Theorem (1970) caps how many faces a d-polytope with n vertices can carry, with cyclic polytopes achieving the cap. The stakes are computational: the simplex method of [[Mathematical_optimization|linear programming]] walks polytope edges, so polytope diameter bounds constrain [[Operations_research]] itself — Santos (2010) refuted the long-standing Hirsch conjecture, and whether some polynomial diameter bound holds remains open, one of the cleanest unsolved questions touching both [[Geometry]] and [[Algorithmic_efficiency|algorithm design]]. ## The Erdős school: points, lines, and incidences Erdős industrialized the study of finite point sets. The happy-ending theorem (Erdős–Szekeres, 1935): any five points in general position contain a convex quadrilateral, and large convex polygons appear in any sufficiently large set. The Szemerédi–Trotter theorem (1983) caps point–line incidences at the two-thirds power of the product (plus linear terms), and it is tight; distinct-distance counting resisted until Guth and Katz (2010) got within a logarithm of Erdős's conjecture using polynomial partitioning — a method imported from [[Algebraic_geometry]] that has since reorganized incidence [[Combinatorics]]. Convexity contributes its own axioms of finiteness: Helly's theorem (1913) — in ℝᵈ, if every d+1 of finitely many convex sets meet, all meet — with Radon and Carathéodory as companions, results that surface in [[Statistics]] (centerpoints, data depth) and in the sample-complexity arguments of [[Machine_learning]]. ## Lattices: from Minkowski to post-quantum keys A lattice is the integer span of a basis in ℝⁿ — the most disciplined infinite point set. Minkowski's convex body theorem (1896) launched the geometry of numbers: any origin-symmetric convex body of volume > 2ⁿ det(Λ) contains a nonzero lattice point. The computational turn came with LLL basis reduction (1982), a polynomial-time [[Algorithm]] that finds short, near-orthogonal bases — strong enough to factor rational polynomials inside [[Computer_algebra]] and to break knapsack ciphers, yet far from solving the shortest-vector problem exactly. On that hardness now rests lattice-based [[Cryptography]]: schemes standardized by NIST in 2024 encrypt against adversaries armed with [[Quantum_computing|quantum computers]], because no known quantum [[Algorithmic_efficiency|speedup]] tames high-dimensional lattices. The same objects organize [[Discrete_mathematics|integer programming]] relaxations and the sieve ideas behind modern factoring — lattice geometry as an engine of both attack and defense. ## Codes are packings: geometry in Hamming space [[Claude_Shannon|Shannon's]] 1948 channel theorem is a packing statement: reliable communication means placing codewords as non-overlapping spheres in signal space, and capacity is the packing's rate ceiling — [[Information_theory]] as high-dimensional [[Geometry]]. In the discrete metric of Hamming space, a code correcting t errors is exactly a packing of radius-t balls, so the best codes of [[Error_detection_and_correction]] are densest packings by definition; the binary Golay code and the Leech lattice constructions built for dimension 24 are two faces of one object. Delsarte's linear-programming bounds (1973) and their descendants — the same [[Mathematical_optimization|optimization]] machinery behind Viazovska's proof — give the strongest known ceilings in both worlds. Geometry pays operationally: lattice quantizers shape the [[Quantization_(signal_processing)|quantization]] noise of [[Digital_signal_processing]], and random geometric [[Graph_theory|graphs]] over point sets model the connectivity of wireless [[Network_science|networks]]. **On the spine:** [[Polytope]] · [[Tessellation]] · [[Combinatorics]] · [[Computational_geometry]] · [[Finite_geometry]]. ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Discrete_geometry) : [Wikitube](https://en.wikitube.io/wiki/Discrete_geometry) ## Previous hub tags Hubs: `Systems`. Portals: [[PORTAL_Graph_theory]], [[PORTAL_Decision_theory]], [[PORTAL_Information_theory]], [[PORTAL_Control_theory]], [[PORTAL_Operations_research]]. --- *Repopulated 2026-08-12 · redlink fill · 0 deletions.*