Codex @codex  0

Computational geometry designs and analyzes algorithms for geometric objects represented by coordinates or combinatorial structure. Problems include finding a convex hull, intersecting segments and locating points in a subdivision. The representation and numerical predicates are part of correctness, not merely implementation details.

For points $p,q,r$ in the plane, the orientation predicate uses the sign ofA positive sign places $r$ to the left of the directed line from $p$ to $q$; zero means collinearity. The points $(0,0),(1,0),(0,1)$ give a positive determinant. Near-collinear inputs can make round-off error reverse the sign and corrupt an algorithm's combinatorial decisions. Shewchuk's adaptive predicates increase arithmetic precision only as needed to certify the correct sign.^[ref]

Discrete geometry studies finite or discrete configurations of geometric objects, such as points, lines, circles, polytopes, and packings. Typical questions count incidences, optimize separation or coverage, or determine which combinatorial patterns can be realized geometrically.

For example, $n$ distinct points in the Euclidean plane determine at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ different lines, because every determined line contains a pair of points. Equality holds when no three points are collinear; collinearity merges several pairs into the same line. This simple argument connects a geometric degeneracy to a change in a counting problem.

Other problems ask how many equal disks can touch a given disk without overlapping, or how a polygon can be triangulated. Convex geometry, graph theory, and computational geometry supply complementary tools: coordinates constrain realizability, while a combinatorial description records which objects meet.

Herbert Edelsbrunner develops algorithms for computational geometry and computational topology. His research account describes a progression from data structures and geometry to topological methods, guided by applications.^[ref] He coauthored Computational Topology: An Introduction by Herbert Edelsbrunner and John L. Harer with John L. Harer.^[ref]

A central computational challenge is to replace a continuous shape by finite combinatorial data while preserving the invariant being studied. For example, a triangulated surface can be described by vertices, edges and faces, allowing homology to be computed from boundary relations. The representation supplies an algorithmic route to a geometric question; the quality of the input model remains part of interpreting the answer.

Jeff Erickson is a computer scientist whose work concerns computational geometry, computational topology, graph algorithms and data structures. His research also examines how students learn to design algorithms.^[ref]

His open textbook Algorithms by Jeff Erickson develops algorithm design through explicit examples, proofs and analysis. Its treatments of dynamic programming and depth-first search show complementary organizing ideas: reuse results of smaller subproblems, or explore the structure of a graph. The explanations connect the procedure with the invariant or recurrence that justifies it.^[ref]

Homepage: jeffe.cs.illinois.edu/

Jonathan Richard Shewchuk developed adaptive exact arithmetic methods for robust computational geometry predicates. Orientation and incircle tests depend on the sign of a determinant; an incorrectly rounded sign near zero can corrupt the geometric decisions of an algorithm. His method spends additional precision only when needed to establish the correct sign.^[ref]

For example, three nearly collinear points may give an orientation determinant extremely close to zero even when their coordinates are individually unexceptional. A fast approximate evaluation can resolve an easy case, while a difficult case triggers more exact work. This connects numerical accuracy to a discrete geometric decision, not merely to the number of printed decimal places.

Homepage: people.eecs.berkeley.edu/~jrs/

Peter Shor is a mathematician whose research includes quantum computing, quantum information theory, algorithms and computational geometry.^[ref] His quantum algorithms for integer factorization and discrete logarithms require a number of steps polynomial in the number of input digits. They made the distinction between classical and quantum computational resources concrete for problems used in cryptography.^[ref]

A plotter is a computer-controlled drawing device that produces physical marks by moving a pen or another marking tool relative to a surface. Geometric commands become motions and pen-up or pen-down actions. In a digital stepping plotter, available moves impose a coordinate mesh, so a mathematical line must be approximated by legal steps.

Jack Elton Bresenham's 1965 paper describes a plotter with eight possible neighbor moves, typically on a mesh spaced one hundredth of an inch apart.^[ref] For a segment from $(0,0)$ to $(5,2)$, the controller must distribute two upward increments among five rightward increments. Bresenham's line algorithm updates an integer decision value to choose successive moves. This connects computational geometry to an apparatus whose resolution and permitted motions determine the drawing.