Fact-checked by Grok 2 weeks ago

Computational geometry

Computational geometry is a branch of computer science that focuses on the design, analysis, and implementation of algorithms for solving geometric problems, typically involving discrete objects such as points, lines, polygons, and circles in two- or three-dimensional space.^[1] It emerged as a distinct discipline in the early 1970s, with the term coined by Michael Ian Shamos in 1973 during his work at Yale University on problems like computing Voronoi diagrams and closest pairs of points.^[2] The field developed rapidly through the late 1970s and 1980s, building on generalizations of one-dimensional sorting and searching algorithms to higher dimensions, and by the 1990s, it had established its own conferences, journals, and a substantial body of research.^[1]^[2] Key topics in computational geometry include computing convex hulls, line segment intersections, triangulations, Voronoi diagrams, Delaunay triangulations, and geometric searching structures like range trees and kd-trees, often achieving optimal time complexities such as O(n log n) for fundamental problems under the real RAM model.^[1]^[3] These algorithms emphasize exact computations with real numbers and asymptotic worst-case analysis, though practical implementations must address issues like numerical precision.^[1] Applications span diverse areas, including computer graphics for rendering and collision detection, robotics for motion planning and pathfinding, geographic information systems (GIS) for spatial queries and mapping, computer-aided design (CAD/CAM) for solid modeling, and scientific computing fields like computational fluid dynamics.^[1]^[3] More recent advancements incorporate approximation algorithms for high-dimensional data and integration with machine learning for tasks like shape analysis.^[1]

Overview

Definition and Scope

Computational geometry is a branch of computer science and mathematics dedicated to the design, analysis, and implementation of efficient algorithms for solving geometric problems involving points, lines, polygons, and solids.^[4] These algorithms process discrete geometric objects, typically in two-dimensional (2D) or three-dimensional (3D) Euclidean spaces, to compute properties or structures such as intersections, enclosures, or proximities.^[5] The field distinguishes between two primary branches: combinatorial computational geometry, which focuses on exact, discrete solutions often assuming integer coordinates to avoid numerical instability and ensure combinatorial optimality, and numerical computational geometry, which addresses approximate solutions using floating-point arithmetic to model continuous real-world geometries with inherent precision limitations.^[6] Combinatorial approaches emphasize worst-case guarantees and topological properties, while numerical methods prioritize practical approximations for curved or high-precision inputs.^[7] The scope of computational geometry centers on achieving efficiency in time and space complexity for large inputs, where brute-force methods often require O(n²) operations for n objects, but optimized algorithms frequently attain O(n log n) worst-case performance through techniques like sorting and divide-and-conquer.^[8] This emphasis extends to both 2D problems, which form the foundational core due to their tractability, and 3D extensions, which introduce added complexity in dimensionality but share similar efficiency goals.^[5] Interdisciplinary ties link computational geometry to algorithm design, data structures, and optimization, enabling solutions to core challenges like proximity problems—such as identifying closest pairs among points—and partitioning problems—such as subdividing space based on geometric attributes.^[9] These connections underpin applications in areas including computer graphics for rendering and robotics for path planning.^[10]

History

The roots of computational geometry lie in ancient Greek mathematics, particularly in Euclid's Elements (c. 300 BC), which systematized geometric constructions as step-by-step procedures using a ruler and compass, laying the groundwork for algorithmic approaches to geometric problems such as polygon formation and circle inscriptions.^[11] These methods emphasized exact constructions from basic primitives, influencing later computational interpretations of geometry as a discrete, verifiable process.^[12] In the 19th and early 20th centuries, precursors emerged through the integration of analytic geometry and numerical methods, with René Descartes' coordinate system (1637) enabling algebraic representations of geometric objects suitable for computation.^[13] By the mid-20th century, applications in computer-aided design advanced the field; notably, A. R. Forrest's 1971 work introduced "computational geometry" in the context of curve and surface modeling for interactive design systems, addressing representation and synthesis of shapes in numerical control.^[14] The modern discipline of computational geometry was formally established in the 1970s, with Michael I. Shamos coining the term in 1973 during his doctoral research at Yale, focusing on combinatorial algorithms for problems like Voronoi diagrams and convex hulls.^[2] Shamos' 1978 Ph.D. thesis further solidified these foundations, demonstrating efficient O(n log n) methods for proximity and range searching.^[15] Franco P. Preparata collaborated closely with Shamos, and their 1985 book Computational Geometry: An Introduction became a seminal text, unifying core problems in both combinatorial and numerical branches while presenting algorithms for hull computation, intersection detection, and triangulation.^[13] The 1980s and 1990s marked rapid institutional growth, with the first Symposium on Computational Geometry (SoCG) held in 1985 in Baltimore, fostering annual exchanges on algorithmic advances.^[16] This was followed by the launch of the journal Computational Geometry: Theory and Applications in 1991 by Elsevier, providing a dedicated venue for theoretical and applied research.^[17] Preparata and Shamos remained pivotal figures, with Preparata's contributions to multidimensional algorithms and Shamos' emphasis on practical implementations shaping the field's trajectory toward robust data structures and query problems.^[2]

Fundamental Concepts

Geometric Primitives

In computational geometry, geometric primitives serve as the foundational building blocks for representing and manipulating spatial data, typically in Euclidean spaces of low dimension such as \mathbb{R}^2 or \mathbb{R}^3. These primitives include points, lines, line segments, polygons, and circles, each defined through mathematical representations that facilitate algorithmic processing. Higher-level primitives, such as convex sets and simplices, extend these basics by incorporating convexity properties essential for optimization and decomposition tasks. Points are the simplest primitives, denoted as coordinate tuples in \mathbb{R}^d. In two dimensions, a point p is represented as (p_x, p_y), where p_x and p_y are real numbers specifying positions along orthogonal axes. In three dimensions, points extend to (p_x, p_y, p_z). The Euclidean distance between two points p and q in \mathbb{R}^d, which measures the straight-line separation, is given by the formula

d(p, q) = \sqrt{\sum_{i=1}^d (p_i - q_i)^2},

derived from the Pythagorean theorem in vector spaces.^[18]^[19] Line segments connect two points and represent finite portions of lines, parameterized as (1-t)a + t b for endpoints a and b with parameter t \in [0,1]. Full lines extend infinitely and can be defined implicitly by the equation ax + by + c = 0 in 2D or by two distinct points. Polygons are closed chains of line segments, specified by an ordered list of vertices p_0, p_1, \dots, p_{n-1} with p_n = p_0; simple polygons have non-intersecting edges except at vertices, whereas self-intersecting polygons cross themselves. Circles in 2D are defined by a center point (h, k) and radius r > 0, satisfying the equation (x - h)^2 + (y - k)^2 = r^2; their 3D analogs, spheres, follow (x - h)^2 + (y - k)^2 + (z - l)^2 = r^2.^[20]^[18] Orientation predicates provide fundamental tests on point configurations, crucial for determining relative positions. In 2D, the orientation of points a, b, and c is assessed via the sign of the scalar (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x): positive indicates a counterclockwise turn (left orientation), negative a clockwise turn (right), and zero collinearity. This predicate, equivalent to the determinant of vectors \overrightarrow{ab} and \overrightarrow{ac}, underpins decisions in algorithms like convex hull construction. Robust implementations ensure exact evaluation even under floating-point arithmetic.^[18]^[21] Higher-level primitives include convex sets, which contain the line segment joining any pair of their points and can be expressed as intersections of half-planes defined by linear inequalities. In 2D, a convex set is the intersection of half-planes \{ (x,y) \mid ax + by + c \geq 0 \}. Simplices generalize triangles and tetrahedra: a 2D simplex is the convex hull of three non-collinear points forming a triangle, while a 3D simplex is the convex hull of four non-coplanar points forming a tetrahedron; in general, a d-simplex is the convex hull of d+1 affinely independent points in \mathbb{R}^d.^[13]^[22] Computational geometry predominantly employs the Cartesian coordinate system, where positions are measured along perpendicular axes, enabling straightforward vector operations and distance calculations. Polar coordinates, specifying points via radius \rho \geq 0 and angle \theta as x = \rho \cos \theta, y = \rho \sin \theta, are used in scenarios involving rotational invariance, such as circle-related computations. While real-valued coordinates support general positioning, integer coordinates facilitate exact arithmetic, preserving computational precision without approximation errors. These primitives form the basis for operations like intersection detection in more advanced problems.^[23]^[5]^[21]

Basic Computational Problems

Basic computational problems in computational geometry address core tasks on geometric primitives, such as points in the plane and line segments, to identify relationships like proximity, intersections, or enclosing structures. These problems form foundational building blocks for advanced geometric processing, with computational goals centered on efficiency: naive approaches often require quadratic time O(n²) by examining all pairs of objects, but optimized methods leverage sorting or spatial partitioning to achieve linearithmic time O(n log n) in the worst case.^[24] Proximity problems focus on measuring and identifying nearness among points. The closest pair problem, given a set of n points in the Euclidean plane, seeks the pair with the minimum distance between them; this serves as a basic measure of spatial density and has applications in clustering and facility location.^[24] The all-nearest neighbors problem extends this by computing, for each point in the set, the nearest other point under the Euclidean metric, providing a complete proximity graph for the input.^[24] Intersection detection determines overlaps between geometric objects, essential for tasks like collision detection and rendering. In the line segment intersection problem, all pairs of intersecting segments from a collection of n segments in the plane are reported, with the output size potentially reaching O(n²) in degenerate cases but typically smaller.^[25] Polygon clipping computes the intersection of a subject polygon with a convex clip polygon, yielding the portion inside the clip boundary; the Sutherland-Hodgman method processes the subject polygon's edges sequentially against each clip edge to produce the clipped result efficiently for convex clips.^[26] Partitioning problems decompose a point set into non-overlapping regions or a mesh of triangles. Triangulation of a point set forms a maximal set of non-crossing edges connecting the points, dividing the convex hull into triangles without adding vertices.^[24] The Delaunay triangulation is a distinguished triangulation that maximizes the minimum angle over all possible triangulations of the same points, promoting equilateral-like triangles for numerical stability in simulations.^[24] Voronoi diagrams partition the plane into cells, each comprising all locations closer to one site (a point from the set) than to any other under the Euclidean distance, dual to the Delaunay triangulation.^[24] Enclosure problems identify compact convex structures containing the input. The convex hull of a point set is the smallest convex polygon enclosing all points, equivalent to the boundary of their convex combination.^[27] The minimum spanning tree for a geometric complete graph on the points connects all vertices with edges of minimum total Euclidean length while forming no cycles, often derived from proximity information like the Delaunay triangulation.^[24]

Combinatorial Computational Geometry

Static Problems

Static problems in combinatorial computational geometry focus on computing discrete structures from a fixed input of geometric objects, such as points or line segments, in the Euclidean plane, typically assuming general position and exact arithmetic. These problems emphasize batch processing without updates or queries, yielding outputs like partitions or graphs whose sizes influence runtime complexity. Key challenges include handling degeneracies and achieving optimal time bounds, often through sorting, sweeping, or decomposition techniques, with algorithms designed for low-dimensional (primarily 2D) settings. A foundational static problem is computing the convex hull of a set of n points in the plane, which forms the smallest convex polygon enclosing all points. The Graham scan algorithm achieves this in O(n \log n) time by first selecting the lowest point as a pivot, sorting the remaining points by polar angle relative to the pivot, and then iteratively constructing the hull using a stack to eliminate non-convex turns.^[27] For output-sensitive performance, the Jarvis march (also known as the gift-wrapping algorithm) runs in O(n h) time, where h is the number of vertices on the hull; it begins at the leftmost point and successively selects the next hull vertex by finding the point that forms the minimal angle with the current edge, wrapping around the boundary like gift paper.^[28] Another core problem involves Voronoi diagrams and their dual, Delaunay triangulations, for a set of n point sites in the plane. A Voronoi diagram partitions the plane into cells where each cell consists of points closer to its site than to any other, computed efficiently by Fortune's sweep-line algorithm in O(n \log n) time; the method simulates a parabolic wavefront advancing across the plane, maintaining a beach line of parabolic arcs and using a priority queue for event handling to trace cell boundaries.^[29] The Delaunay triangulation, which connects sites to form triangles maximizing the minimum angle, is the straight-line dual of the Voronoi diagram and satisfies the empty circle criterion: the circumcircle of every triangle contains no other site in its interior, ensuring local optimality and uniqueness under general position.^[30] This dual relationship allows Delaunay triangulations to be derived directly from the Voronoi output in linear additional time. Triangulating a simple polygon with n vertices—decomposing it into n-2 non-overlapping triangles using non-crossing diagonals—is a classic static problem with applications in polygon processing. Chazelle's deterministic algorithm accomplishes this in optimal O(n) time by constructing a hierarchical trapezoidal decomposition and using a finger-searching data structure to find short diagonals efficiently, marking a breakthrough in linear-time exact computation for polygons.^[31] A simpler, quadratic-time alternative is the ear-clipping method, which relies on the two-ears theorem stating that every simple polygon with more than three vertices has at least two ears (triangles formed by three consecutive vertices where the diagonal lies inside the polygon); the algorithm iteratively identifies and clips an ear, updating the boundary, until only a triangle remains, running in O(n^2) time due to repeated scans for ears.^[32] Map overlay, which computes the arrangement of n line segments by finding all their intersections to form a planar map, is essential for overlaying multiple geometric maps. The Bentley-Ottmann sweep-line algorithm reports all k intersection points in O((n + k) \log n) time, output-sensitive to the complexity of the arrangement; it sweeps a vertical line across the plane, maintaining the ordered status of active segments in a balanced binary search tree and using a priority queue for potential intersection events, processing endpoints and crossings as they occur.^[25] These algorithms highlight the prevalence of sweep-line paradigms in 2D static problems, balancing preprocessing costs with output size for practical efficiency.

Dynamic and Query Problems

Dynamic maintenance of geometric structures addresses the challenge of efficiently updating data sets under insertions and deletions while supporting queries on evolving configurations. A seminal approach for maintaining the convex hull of a dynamic set of points in the plane is the structure proposed by Overmars and van Leeuwen, which supports both insertions and deletions in O(log² n) time per operation, where n is the current number of points, using a hierarchical tree representation that balances update costs across levels.^[33] This fully dynamic method builds upon static convex hull computations by allowing incremental additions and removals without full recomputation, achieving polylogarithmic amortized costs for a sequence of operations.^[34] Geometric queries in dynamic settings require data structures that preprocess evolving geometric objects to answer location-based or proximity questions efficiently. For point location in a planar subdivision, Kirkpatrick's algorithm preprocesses a connected planar graph with n vertices in O(n log n) time to support queries in O(log n) time, by constructing a hierarchy of successively coarsened triangulations that preserves connectivity while reducing size by a constant factor at each level. This structure has been extended for dynamic subdivisions to allow localized updates with minimal rebuilding.^[35]^[36] Range searching extends point location to report all points within a query region, such as an axis-aligned rectangle in the plane. In two dimensions, multidimensional range trees achieve O(n log n) preprocessing time and space, supporting orthogonal range reporting queries in O(log² n + k) time, where k is the number of reported points, by decomposing the space into nested trees that prune irrelevant subranges during traversal.^[37] For dynamic variants, fractional cascading techniques reduce query times to near-linear in the output size while handling updates in O(log² n) amortized time, balancing space and speed trade-offs for applications like database retrieval.^[38] Nearest neighbor searches identify the closest point in a set to a query location, often leveraging Voronoi diagrams for efficient partitioning. Constructing a Voronoi diagram of n sites in O(n log n) time enables O(log n) query time for nearest neighbor searches via point location in the diagram's dual Delaunay triangulation, as each Voronoi cell corresponds to the region dominated by a single site.^[9] This method trades higher preprocessing for faster queries compared to naive linear scans, with dynamic extensions using topological changes to update the diagram in O(log n) per insertion under certain assumptions.^[39] Trapezoidal maps provide a decomposition of the plane induced by line segments, facilitating ray shooting and segment intersection queries. By extending vertical rays from each endpoint and vertex to form trapezoids, the map supports ray shooting—finding the first segment intersected by a query ray—in O(log n + k) time after O(n log n) preprocessing, using a search tree over the trapezoids for initial localization followed by linear traversal along the ray.^[40] This structure is adaptable to dynamic settings for intersection detection, where updates to segments trigger localized refinements to adjacent trapezoids, preserving overall query efficiency.^[41] Amortized analysis plays a key role in evaluating batched updates for dynamic geometric data structures, accounting for occasional expensive rebuilds across sequences of operations. For instance, in maintaining range searching structures under batches of insertions and deletions, techniques like global rebuilding every O(n / log n) updates ensure O(log n) amortized time per operation, spreading the O(n log n) rebuild cost while keeping individual queries responsive.^[42] This approach is particularly useful in geometric set cover or hull maintenance, where batched processing amortizes the overhead of structural invariants.^[43]

Numerical Computational Geometry

Approximation and Error Handling

In numerical computational geometry, floating-point arithmetic poses significant challenges due to round-off errors, which arise from the limited precision of representations like IEEE 754 double-precision numbers. These errors are particularly pronounced in distance calculations, where operations such as computing the Euclidean distance \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} can suffer from instability in the square root function, especially when arguments are near zero or when subtracting nearly equal quantities (catastrophic cancellation).^[44] In iterative methods, such as those for optimization or subdivision in mesh generation, these errors accumulate over multiple steps, potentially leading to divergent results or incorrect topological decisions, like misclassifying point orientations in Delaunay triangulations.^[44] To address these issues while prioritizing efficiency, approximation algorithms trade exactness for computational speed, often achieving high-quality results in practice. For convex hull computation, ε-approximation techniques construct a hull that approximates the exact one (e.g., in Hausdorff distance, implying area within a factor close to 1 + ε for small ε), with algorithms running in O(n + 1/ε) time for planar point sets.^[45] Similarly, randomized sampling provides an effective method for computing the exact diameter of a point set—the maximum pairwise distance—by selecting subsets likely to include the extremal pair; Clarkson and Shor's Las Vegas algorithm achieves an expected O(n log n) time complexity in fixed dimensions by reducing the problem to spherical intersections via random sampling.^[46] These methods are particularly valuable in large-scale applications where exact combinatorial solutions, while ideal in theory, become infeasible due to numerical instability. Interval arithmetic offers a strategy for adaptive precision by representing coordinates or computation results as closed intervals [a, b], allowing bounds on possible error propagation to guarantee correctness without full exact arithmetic. In geometric computations, this enables dynamic filters that quickly discard impossible cases using floating-point evaluations and refine precision only when intervals overlap critically, as demonstrated in implementations for predicates like incircle tests.^[47] By enclosing input coordinates in tight intervals and propagating them through operations (e.g., addition yields [a_1 + a_2, b_1 + b_2]), algorithms can certify that results lie within specified error tolerances, balancing speed and reliability in robust geometric software.^[47] Core numerical problems in this domain often involve solving overdetermined systems via least squares. For circle fitting, the geometric least-squares approach minimizes the sum of squared radial errors \sum_i (r_i - r)^2, where r_i is the distance from the fitted center to the i-th data point and r is the radius; this nonlinear optimization can be solved iteratively starting from an algebraic approximation, ensuring the fitted circle best matches noisy point data in applications like computer vision.^[48] Spline interpolation extends this to curve approximation, constructing piecewise polynomial curves (typically cubic) that pass through or near control points while minimizing curvature variations; in computational geometry, B-spline representations facilitate smooth approximations of scattered data for surface modeling, with stable algorithms solving tridiagonal systems for knot insertion and coefficient computation.^[49] Error metrics distinguish between absolute and relative measures to quantify approximation quality. Absolute error captures the raw deviation, such as the Euclidean distance between exact and approximate points, which is straightforward but scale-dependent. Relative error, defined as |\hat{x} - x| / |x| for a value x, normalizes this to reveal proportional inaccuracies, proving more insightful in geometric contexts where scales vary. In 3D modeling, uncontrolled absolute errors can perturb geometry sufficiently to induce self-intersections or invalid topologies in meshes, whereas relative errors help maintain proportional fidelity across feature sizes.^[50]

Robustness and Exact Computations

In computational geometry, robustness refers to the ability of algorithms to produce correct outputs despite numerical instabilities arising from floating-point arithmetic, such as rounding errors that can lead to incorrect predicate evaluations.^[44] These issues are particularly pronounced in geometric computations where small perturbations can alter topological properties, like the orientation of points or the emptiness of circles. To address this, exact geometric predicates ensure precise sign determinations without relying solely on machine precision. Exact geometric predicates form the foundation of robust computations, providing reliable tests for fundamental relations between points. The orientation test for three points p_1 = (x_1, y_1), p_2 = (x_2, y_2), and p_3 = (x_3, y_3) determines if they form a left turn, right turn, or collinear configuration by evaluating the sign of the determinant:

\det \begin{vmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{vmatrix} = (x_2 - x_1)(y_3 - y_1) - (x_3 - x_1)(y_2 - y_1).

A positive value indicates a counterclockwise orientation, negative a clockwise one, and zero collinearity.^[44] Similarly, the incircle test for four points assesses whether one point lies inside the circle defined by the other three, using a 4x4 determinant whose sign reveals the relative position; this predicate is crucial for Delaunay triangulations and Voronoi diagrams.^[44] These predicates, when implemented exactly, avoid the pitfalls of floating-point errors by computing results to arbitrary precision. Symbolic perturbation techniques, such as adaptive arithmetic, enhance efficiency while maintaining exactness. Jonathan Shewchuk's method uses filtered floating-point evaluations to approximate predicates quickly, falling back to exact rational arithmetic only when uncertainty arises, thus achieving robustness without the overhead of full-precision computations in most cases.^[44] This approach symbolically perturbs degenerate inputs infinitesimally to resolve ties, ensuring generic algorithms handle collinear or cocircular points seamlessly without explicit case analysis. Exact arithmetic libraries provide practical implementations for robust geometric computing. The LEDA library offers an exact kernel that performs predicates using rational arithmetic with floating-point filters for speed, supporting 2D and higher-dimensional geometry with guaranteed correctness.^[51] Similarly, CGAL (Computational Geometry Algorithms Library) enables robust constructions through multiprecision number types like those from GMP, combined with lazy exact evaluations that defer high-precision computations until necessary.^[52] Degeneracy handling in these systems leverages generic programming to abstract predicates and constructions, allowing algorithms to resolve issues like collinear points or cocircular configurations transparently. In CGAL, this is achieved via traits classes that parameterize kernels, enabling degeneracy-free execution by substituting exact predicates without modifying core algorithm logic.^[53] Certification techniques extend this robustness to verify computational results, such as ensuring a triangulation is Delaunay despite noisy input coordinates. Controlled perturbations in CGAL allow provable correctness for 2D Delaunay triangulations in O(n log n) time, where infinitesimal shifts certify the output topology against floating-point perturbations.^[54]

Algorithms and Data Structures

Paradigms and Techniques

Computational geometry employs several fundamental algorithmic paradigms that provide reusable frameworks for solving a wide range of geometric problems efficiently. These techniques leverage the structure of geometric data to achieve optimal or near-optimal time complexities, often by exploiting spatial relationships and reducing the search space systematically.^[55] The sweep line paradigm involves moving a conceptual line, typically vertical, across the plane from left to right, processing events such as segment endpoints or intersection points in sorted order. This approach maintains a dynamic status structure for the active segments intersected by the sweep line, allowing efficient updates and queries. A seminal application is the Bentley-Ottmann algorithm, which reports all intersections among n line segments in O((n + k) \log n) time, where k is the number of intersections, by handling O(n \log n + k) events.^[56] Divide-and-conquer is another core technique, recursively partitioning the input into smaller subproblems, solving them independently, and then combining results while handling interactions across boundaries. For the closest pair of points problem among n points in the plane, the algorithm divides the set by a vertical midline, recursively finds the minimum distance \delta in each half, and then checks a strip of width $2\delta around the midline, limiting candidates to at most seven points per side due to pigeonhole principles, achieving O(n \log n) time overall.^[57] Incremental construction builds geometric structures by adding elements one by one, updating the current configuration after each insertion. To achieve efficiency, randomization is often used to bound expected costs by ensuring uniform conflict probabilities. For instance, randomized incremental construction of trapezoidal maps from n line segments yields an expected O(n \log n) time by adding segments in random order and resolving conflicts with backward analysis, avoiding worst-case degeneracies.^[58] Duality transforms provide a powerful mapping between primal and dual spaces to simplify incidence and order relations. In the standard point-line duality, a point (a, b) maps to the line y = ax - b, and a line y = mx + c maps to the point (m, -c); this preserves incidences (a point on a line dualizes to a line through a point) and supports collinearity via concavity, facilitating algorithms for envelopes and arrangements.^[55] Backtracking with pruning explores search trees depth-first but discards branches that cannot lead to valid or optimal solutions, guided by geometric constraints to minimize exponential growth. The prune-and-search paradigm exemplifies this by tentatively evaluating a candidate solution to prune a constant fraction of the input, recursing on the remainder, and achieving linear expected time for optimization problems like the smallest enclosing disk.^[59] These paradigms often combine, as in applying duality to convex hull computations or sweep lines to Voronoi diagrams, enabling modular solutions across static and dynamic settings.

Key Geometric Structures

In computational geometry, key data structures are essential for efficiently representing, storing, and querying geometric entities such as points, lines, and planar subdivisions. These structures enable operations like traversal, searching, and updates while maintaining topological and spatial relationships. They form the foundation for solving complex problems by providing logarithmic-time access and balanced organization, often leveraging tree-based hierarchies to handle large datasets. A primary structure for planar subdivisions is the Doubly-Connected Edge List (DCEL), which represents the topology of a plane graph embedding. The DCEL consists of records for vertices, edges, and faces, where each directed edge (half-edge) points to its origin vertex, twin half-edge, next and previous half-edges around a face, and incident face. This bidirectional linking allows constant-time access to adjacent elements, facilitating efficient navigation and modifications in arrangements of lines or polygons. The structure supports operations like edge insertion or face splitting in amortized linear time relative to local changes, making it indispensable for map overlays and Voronoi diagrams.^[10] For indexing points in multi-dimensional space, the k-d tree (k-dimensional tree) provides a space-partitioning mechanism. Constructed by recursively selecting an axis (alternating cyclically) and splitting the point set at its median, the tree organizes points into a binary hierarchy that approximates balanced splits. This enables efficient nearest-neighbor searches, with expected O(log n) query time for n points in low dimensions, by traversing to the relevant leaf and backtracking with bounding checks. K-d trees are particularly effective for exact and approximate proximity queries in 2D and 3D, though performance degrades in high dimensions due to the curse of dimensionality.^[60] Quadtrees extend this partitioning to 2D regions, recursively dividing a bounding square into four equal quadrants until a homogeneity criterion (e.g., single point or uniform density) is met. Each internal node represents a square with four child pointers to subquadrants, while leaves store geometric primitives or occupancy flags. This structure excels in spatial indexing for raster data or collision detection, supporting range queries like window searches in O(log n + k) time, where k is the number of reported objects. Variants such as point quadtrees and region quadtrees adapt to discrete or continuous data, with compression techniques reducing storage for sparse distributions.^[61] Range trees address orthogonal range queries on point sets, using a multi-level tree where the primary tree is a balanced BST on one coordinate (e.g., x), and each node contains a secondary BST on the orthogonal coordinate (e.g., y). For d dimensions, this nests d levels, allowing canonical decomposition of query rectangles into O(log^d n) subtrees. Standard implementations yield O(log^d n + k) query time and O(n log^{d-1} n) space, but fractional cascading—chaining sorted lists across levels—reduces the query to O(log^{d-1} n + k) by avoiding redundant traversals in secondary trees. In 2D, this achieves O(log n + k) queries after O(n log n) preprocessing.^[62] Persistent data structures enable non-destructive updates, maintaining multiple versions of a geometric configuration like a convex hull while sharing unchanged parts across versions. For dynamic convex hull maintenance, persistent balanced search trees store hull edges sorted by slope, allowing insertions and deletions in O(log^2 n) time per operation and supporting queries on any historical version in similar time. This approach, using path copying for persistence, preserves historical hulls for applications like motion planning with timestamps, with overall space O(n log n).^[63] To ensure logarithmic height and balanced performance, these geometric structures incorporate self-balancing binary search trees adapted for spatial or angular keys. AVL trees, which maintain height balance via single or double rotations after updates (keeping subtree height differences at most 1), are used for ordering points or slopes, guaranteeing O(log n) operations. Red-black trees, enforcing balance through color invariants (no two consecutive red nodes, equal black-height paths), offer similar bounds with fewer rotations on average, making them suitable for dynamic insertions in range trees or hull maintenance. Both are integrated with geometric comparators, such as coordinate or polar angle keys, to handle degeneracies.^[10]

Applications

Computer Graphics and CAD

In computer graphics, computational geometry plays a pivotal role in rendering pipelines, particularly through techniques for ray tracing and visibility determination. Ray tracing simulates light paths by computing intersections between rays and geometric primitives, often triangles, to generate realistic images. A key algorithm for efficient ray-triangle intersection is the Möller-Trumbore method, which avoids explicit plane equation computation by using vector cross products and barycentric coordinates to determine if and where a ray hits a triangle, achieving high performance with minimal storage. This approach is widely used in production renderers for its speed and simplicity in handling oriented triangles. Visibility resolution in rasterization pipelines relies on the z-buffer algorithm, which maintains a depth value for each pixel to discard fragments farther from the viewer during rendering. Introduced as part of early curved surface subdivision techniques, the z-buffer performs depth tests to resolve hidden surfaces without sorting primitives, enabling efficient rendering of complex scenes by processing fragments in arbitrary order.^[64] Curve and surface modeling in CAD systems leverages parametric representations from computational geometry for precise design of free-form shapes. Bézier curves provide a foundational method, defined parametrically as

\mathbf{B}(t) = \sum_{k=0}^{n} \binom{n}{k} (1-t)^{n-k} t^k \mathbf{P}_k, \quad t \in [0,1],

where \mathbf{P}_k are control points and \binom{n}{k} are binomial coefficients, allowing smooth interpolation influenced by control polygon tangents. Developed for automotive design, these curves are elevated to surfaces via tensor products for modeling complex contours. For more advanced applications in CAD, Non-Uniform Rational B-Splines (NURBS) extend Bézier curves by incorporating weights and non-uniform knot vectors, enabling exact representation of conics and higher-degree surfaces essential for manufacturing tolerances. NURBS facilitate local control and continuity adjustments, forming the core of systems like those in industrial design software.^[65] Collision detection in animated graphics scenes accelerates by using bounding volume hierarchies (BVH), which organize primitives into a tree of enclosing volumes like axis-aligned bounding boxes to prune unnecessary intersection tests. BVH traversal quickly identifies potential collisions between dynamic objects, reducing computational cost from O(n^2) to near-linear time in practice for animations and simulations.^[66] Mesh generation for finite element analysis employs Delaunay refinement to produce high-quality triangular meshes from geometric domains, ensuring elements meet size and shape criteria for numerical accuracy. The algorithm iteratively adds Steiner points to eliminate small angles and skinny triangles while preserving boundaries, yielding meshes with bounded aspect ratios suitable for stress simulations in CAD.^[67] Integration of these geometric techniques occurs in graphics APIs like OpenGL and DirectX through tessellation shaders, which subdivide patches into denser meshes on the GPU for real-time rendering of detailed surfaces without excessive vertex data transfer. OpenGL's tessellation control and evaluation shaders, introduced in version 4.0, parameterize subdivision based on distance or curvature, while DirectX 11's hull and domain shaders provide analogous functionality for adaptive geometry in games and CAD previews.^[68]^[69]

Robotics and GIS

In robotics, motion planning leverages computational geometry to compute collision-free paths for robots in complex environments. A foundational concept is the configuration space (C-space), which represents all possible positions and orientations of a robot relative to its obstacles, transforming the problem into finding a path in a higher-dimensional space where obstacles become C-space obstacles (C-obstacles).^[70] These C-obstacles are computed by Minkowski sums of the robot's geometry with environmental obstacles, enabling path planning algorithms to treat the robot as a point navigating around expanded barriers.^[70] Sampling-based methods have become widely adopted for high-dimensional C-spaces due to their probabilistic completeness and efficiency. The Probabilistic Roadmap (PRM) algorithm constructs a roadmap by randomly sampling configurations in the free space, connecting nearby collision-free samples with straight-line paths, and querying the graph for paths between start and goal configurations.^[71] Similarly, the Rapidly-exploring Random Tree (RRT) builds a tree rooted at the start configuration by iteratively sampling points and extending the nearest tree node toward them with a fixed step size, ensuring exploration of the space while avoiding obstacles.^[72] These techniques are particularly effective in robotics for tasks like manipulator arm motion or mobile robot navigation in cluttered settings. In Geographic Information Systems (GIS), computational geometry supports spatial analysis through operations like polygon overlay, which computes unions, intersections, or differences of polygonal regions representing land use, boundaries, or environmental features. The Vatti clipping algorithm efficiently handles these by sorting polygon edges and resolving intersections via a sweep-line approach, producing output polygons that preserve topological relationships and attributes for map algebra.^[73] For route planning on terrains, shortest path algorithms adapt Dijkstra's method to geometric constraints, using a continuous Dijkstra variant that propagates wavefronts across polyhedral surfaces to find exact geodesic paths accounting for elevation and obstacles. Sensor fusion in robotics and GIS often involves aligning 3D point clouds from sensors like LiDAR for mapping and reconstruction. The Iterative Closest Point (ICP) algorithm achieves this by iteratively estimating a rigid transformation T that minimizes the sum of squared distances between corresponding points:

\min_{T} \sum_{i} \| T(\mathbf{p}_i) - \mathbf{q}_i \|^2,

where \{\mathbf{p}_i\} and \{\mathbf{q}_i\} are matched point pairs from the source and target clouds, typically found via nearest-neighbor search.^[74] This enables applications such as simultaneous localization and mapping (SLAM) in autonomous systems. Route optimization in geometric settings includes solving the Traveling Salesman Problem (TSP) on graphs where nodes are points in the plane and edges follow Euclidean distances, with approximation schemes like Arora's PTAS providing near-optimal tours in polynomial time for Euclidean instances. Visibility graphs further aid path planning in polygonal environments by connecting vertices that have line-of-sight without intersecting obstacles, allowing shortest path queries via graph search on this structure.^[75] Real-world applications abound, such as GPS navigation systems that use overlay analysis for route computation over layered maps and shortest paths on digital elevation models for efficient travel. In autonomous vehicles, Voronoi diagrams delineate safe paths by maximizing clearance from obstacles, integrating with sampling methods to generate collision-avoiding trajectories in dynamic traffic scenarios.^[76]

Advanced Topics

Higher Dimensions and Variations

Computational geometry problems traditionally formulated in two or three dimensions face significant challenges when extended to higher-dimensional spaces, primarily due to the curse of dimensionality, which leads to exponential growth in computational complexity with respect to the dimension d. For instance, constructing the convex hull of n points in d-dimensions requires time proportional to O(n \log n + n^{\lceil d/2 \rceil}) in the worst case, reflecting the combinatorial explosion of potential facets and the need to examine subsets of points that grow rapidly with d.^[77] Similarly, simplex range reporting—identifying all points within a d-simplex query—suffers from this curse, with data structures achieving preprocessing in O(n^{1 + \lceil d/2 \rceil}) time and O(n^{\lceil d/2 \rceil}) space, while supporting queries in O(n^{\lceil d/2 \rceil - \epsilon} + k) time for output size k, for any fixed \epsilon > 0.^[78] These bounds highlight how even linear-time algorithms in low dimensions become infeasible as d increases, motivating approximations and dimensionality reduction techniques to mitigate the exponential dependencies.^[79] Randomized algorithms provide a powerful approach to alleviate these higher-dimensional challenges by achieving expected running times that are more favorable, particularly in fixed dimensions. The Clarkson-Shor technique, introduced in the late 1980s, employs random sampling to construct geometric structures incrementally, ensuring that each addition step processes a small, probabilistically bounded number of conflicting elements. This method yields expected linear-time algorithms for problems like convex hull computation in fixed d, with overall time O(n) expected, independent of the \lceil d/2 \rceil term in the worst case, by sampling subsets and solving subproblems recursively.^[80] The technique has been extended to other higher-dimensional tasks, such as nearest neighbor searching and linear programming, where random pivoting reduces the expected complexity to near-linear while maintaining high probability of success.^[81] Parallel computational geometry explores models like the PRAM (Parallel Random Access Machine) to exploit concurrency for higher-dimensional problems, aiming for polylogarithmic time with polynomial processors. In the EREW PRAM model, sorting n points by coordinate can be accomplished in O(\log n) time using n processors, serving as a primitive for more complex tasks like convex hull construction, which achieves O(\log n) time with O(n \log n) total work in three dimensions and extends to higher d with similar logarithmic depth but increased processor counts.^[77] For geometric decision problems, such as element uniqueness or simplex containment, circuit complexity analyses reveal that many can be solved in NC (Nick's Class, polylog time with polynomial processors), though some, like general geometric set intersection, are P-complete, resisting efficient parallelization even in low dimensions.^[82] Variations of computational geometry incorporate advanced mathematical structures to handle higher dimensions and complex inputs. Topological persistence, a tool from persistent homology, quantifies the "lifespan" of topological features (e.g., holes and voids) across scales in point cloud data, producing persistence diagrams that summarize multi-dimensional geometric structures robustly. Introduced for analyzing filtrations of simplicial complexes, it computes barcodes or diagrams in O(n^3) time for sparse complexes, enabling applications like shape reconstruction in high-dimensional data where traditional metrics fail due to sparsity.^[83] Complementing this, semi-algebraic sets—regions defined by polynomial inequalities—extend geometric queries in the real RAM model, where arithmetic operations on reals are constant time; range searching over such sets supports queries in O((s/\log n)^{d/2} + k) time after O(n \polylog n) preprocessing, for constant description complexity s, bridging algebraic geometry with efficient data structures.^[84] Despite these advances, higher dimensions impose fundamental limitations, with many core problems exhibiting NP-hardness when d is part of the input or sufficiently large. For example, the closest pair problem, while solvable in O(n \log n + n^{O(d)}) time for fixed d, becomes intractable in very high dimensions due to the exponential factor, and variants like approximate closest pair under certain metrics or with additional constraints (e.g., bichromatic pairs) are proven NP-hard, underscoring the need for heuristics or approximations.^[85] This hardness, combined with the curse of dimensionality, confines exact algorithms to moderate d (typically d \leq 10) in practice, shifting focus to probabilistic and approximate methods for real-world high-dimensional applications.^[86]

Recent Developments

In recent years, computational geometry has increasingly intersected with other fields, yielding advancements that address complex data challenges in topology, machine learning, quantum computing, large-scale processing, and sustainable design. These developments, primarily emerging since 2020, leverage geometric principles to enhance robustness and efficiency in high-dimensional and dynamic environments.^[87] Computational topology has seen significant progress through persistent homology, a tool for analyzing shapes by tracking topological features across scales via filtrations, which produce barcode diagrams visualizing the birth and persistence of holes and connected components. These diagrams enable robust shape analysis by identifying stable features invariant to deformations, such as in noisy or incomplete data sets. In data visualization, persistent homology facilitates the representation of multi-scale structures, allowing users to explore topological summaries of complex point clouds or graphs interactively, with applications in scientific data exploration where traditional metrics fail to capture global connectivity. For instance, barcode diagrams from Vietoris-Rips filtrations have been applied to visualize evolutionary changes in biological shapes, highlighting persistent features for intuitive interpretation.^[88]^[87] Geometric deep learning has advanced by integrating graph neural networks (GNNs) with mesh and point cloud representations, enabling end-to-end processing of irregular geometric data. PointNet, an early yet influential model, processes point clouds through symmetric functions like max-pooling over local neighborhoods to aggregate features invariant to permutations, achieving high accuracy in tasks such as segmentation and classification. Recent extensions build on this by applying GNNs to meshes, where convolutional operations propagate information across edges, improving performance on tasks like 3D object detection and surface reconstruction. Surveys highlight how these methods handle non-Euclidean data, with GNNs on point clouds outperforming traditional approaches in remote sensing applications by capturing local geometric relations efficiently.^[89] Quantum geometric algorithms have explored adaptations of Grover's search to spatial queries, offering potential speedups for problems like nearest neighbor search. By encoding point sets into quantum states and using amplitude amplification, these algorithms achieve a quadratic speedup, reducing the complexity from O(n) to O(\sqrt{n}) queries in unstructured spaces. For fixed-radius nearest neighbor searches, fixed-point variants of Grover's algorithm query oracles to identify neighbors within a radius, with applications in simulating particle interactions where classical methods scale poorly. Quantum k-nearest neighbors further incorporate SWAP tests for similarity measurement, enabling high-probability identification in high dimensions.^[90] In big data contexts, streaming algorithms for massive point sets have advanced through coresets, which approximate geometric properties using small subsets while processing data incrementally. These coresets reduce the input size to O(k / \epsilon^d) points for \epsilon-approximate k-clustering in d dimensions, preserving solution quality with high probability and enabling memory-efficient computation on streams. Recent work extends this to dynamic settings, supporting insertions and deletions for independent set approximations in geometric graphs, crucial for real-time analysis of sensor data. Such techniques transform big data problems into manageable ones, with predictive coresets further incorporating uncertainty estimates for robust learning.^[91]^[92] Sustainability applications have benefited from geometric optimization in renewable energy, particularly wind farm layouts using Voronoi diagrams to model turbine interactions and spacing. Voronoi-based approaches partition the farm area into cells representing each turbine's influence zone, minimizing wake overlaps and maximizing energy yield by optimizing positions under terrain constraints. In offshore settings with heterogeneous turbine types, these diagrams guide cable routing and placement, reducing costs by 12.74% in simulated layouts. Such methods integrate computational geometry with environmental modeling to support scalable, eco-friendly designs.^[93]

References

[1]
[PDF] CMSC 754: Lecture 1 Introduction to Computational Geometry
Computational geometry involves designing and analyzing efficient algorithms for problems with geometric input and output, often in 2D and 3D spaces.
[2]
[PDF] The Early Years of Computational Geometry-a Personal Memoir
Computational geometry (CG) as a discipline is now a quarter-century old and has given rise to several entire journals, scores of conferences and thousands ...
[3]
[PDF] Fundamentals of Computational Geometry
Nov 22, 2022 · Computational geometry is the design and analysis of algorithms for geometric problems in low dimensions, typically two or three dimensions.
[4]
[PDF] Computational Geometry
Computational geometry involves the design, analysis and implementation of efficient algorithms for solving geometric problems, e.g., problems involving ...
[5]
[PDF] CMSC 754 Computational Geometry
Computational geometry involves designing efficient algorithms for problems with geometric input/output, often focusing on 2D and 3D spaces, and flat objects ...
[6]
[PDF] Computational geometry and optimization - IME-USP
main branches of computational geometry are combinatorial computational ... and numerical computational geometry, which deals primarily with.<|control11|><|separator|>
[7]
[PDF] Numerical Issues in Computational Geometry
May 14, 2003 · In most geometric algorithms, there is a separation between the combinatorial structures and the numer- ical calculations. For example, in ...
[8]
[PDF] Computational Geometry: Convex Hulls
In a d-dimensional space, the complexity is O(nd+1). Algorithms. There are many algorithms for computing the convex hull: – Brute Force: O ...
[9]
[PDF] Computational Geometry: Proximity and Location
Typical problems in this area involve computing geometric structures based on proximity, such as the Voronoi diagram, Delaunay triangulation and related graph ...
[10]
[PDF] Computational Geometry Algorithms and Applications
Computational geometry emerged from the field of algorithms design and analysis in the late 1970s. It has grown into a recognized discipline with its own ...
[11]
Euclid's Elements, Introduction - Clark University
It has influenced all branches of science but none so much as mathematics and the exact sciences. The Elements have been studied 24 centuries in many languages ...
[12]
https://farside.ph.utexas.edu/books/Euclid/Elements.pdf
[13]
Computational Geometry: An Introduction (Texts and Monographs in ...
Geometric algorithms involve the manipulation of objects which are not handled at the machine language level. The user must therefore organize these complex ...
[14]
[PDF] COMPUTATIONAL GEOfli7ETRY - Michael I. Shamos
... COMPUTATIONAL GEOMETRY. Michael Ian Shamos. Yale University, 1978 . . This thesis Is a study of the computational aspects of. geometry within the framew~rk of ...
[15]
Proceedings of the first annual symposium on Computational ...
Jun 1, 1985 · SCG '85: Proceedings of the first annual symposium on Computational geometry ; Publisher: Association for Computing Machinery; New York; NY ...
[16]
Computational Geometry | Vol 1, Issue 1, Pages 1-64 (July 1991)
Volume 1, Issue 1 · Pages 1-64 (July 1991) · Editorial board · Editorial · Distinct distances determined by subsets of a point set in space · On rectilinear link ...
[17]
Geometric Primitives - Algorithms, 4th Edition
Dec 22, 2016 · Geometric primitives include points, counterclockwise turns, line segments, intervals, polygons, and bounding boxes.Missing: sources | Show results with:sources
[18]
[PDF] Euclidean Distance Geometry and Applications - UC Davis Math
Abstract. Euclidean distance geometry is the study of Euclidean geometry based on the concept of distance. This is useful in several applications where the ...
[19]
Geometric Primitives - 3D Math Primer for Graphics and Game ...
In computer science and computational geometry, there are variations on these definitions. This book uses the classical definitions for line and line segment.
[20]
Fast Robust Predicates for Computational Geometry
The orientation test determines whether a point lies to the left of, to the right of, or on a line or plane defined by other points. The incircle test ...Missing: source | Show results with:source
[21]
[PDF] Intersection patterns of convex sets via simplicial complexes, a survey
Oct 22, 2011 · Abstract. The task of this survey is to present various results on intersection patterns of convex sets. One of main tools for studying ...
[22]
Polar Coordinate Systems
A polar coordinate space has only one axis, however, sometimes called the polar axis, which is usually depicted as a ray from the origin.
[23]
[PDF] Closest-point Problems - Michael I. Shamos
Closest-point problems include finding the two closest points, k nearest/farthest neighbors, the smallest circle enclosing a set, and a minimum spanning tree.
[24]
[PDF] Algorithms for Reporting and Counting Geometric Intersections. - DTIC
G om.tric Intersections by. Jon L. Bentley 1) and Th. ottmaan. 2). Abstract. An interesting class of “Geometric intersection Probl.ms” calls for dealing with ...
[25]
Reentrant polygon clipping
These algorithms are able to clip polygons against ir- regular convex plane-faced volumes in three dimensions, removing the parts of the polygon which lie ...
[26]
[PDF] the convex hull of a finite planar set - UCSD Math
THE CONVEX HULL OF A FINITE PLANAR SET. R.L. GRAHAM. Bell Telephone Laboratories, Incorporated. Murray Hill, New Jersey, USA. Received 28 January 1972 convex ...Missing: seminal | Show results with:seminal
[27]
https://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf
[28]
A sweepline algorithm for Voronoi diagrams
We present a transformation that can be used to compute Voronoi diagrams with a sweepline technique. The transformation is used to obtain simple algorithms for ...
[29]
[PDF] Two-dimensional Delaunay triangulations - People @EECS
Oct 25, 2012 · The Delaunay triangulation of a point set S, introduced by Boris Nikolaevich Delaunay in. 1934, is characterized by the empty circumdisk ...
[30]
[PDF] Triangulating a Simple Polygon in Linear Time - cs.Princeton
Chazelle and Incerpi [6] showed how to build the visibility map of an n-vertex curve in. O(n log n) time, using divide-and-conquer. Their algorithm mimics ...Missing: paper | Show results with:paper
[31]
[PDF] Ear-clipping Based Algorithms of Generating High-quality Polygon ...
Abstract A basic and an improved ear-clipping based algorithm for triangulating simple polygons and polygons with holes are presented. In the basic version, ...
[32]
Maintenance of configurations in the plane - ScienceDirect.com
We establish a fully dynamic maintenance algorithm for convex hulls that can process insertions and deletions of single points in only O(log 2 n) steps per ...
[33]
[PDF] Three Problems about Dynamic Convex Hulls - Timothy M. Chan
Feb 13, 2012 · By the end of this paper, all of the three current dynamic convex hull techniques—Overmars and van Leeuwen's hull trees [33] and the ...
[34]
[PDF] optimal search in planar subdivisions - UBC Computer Science
Our basic point location algorithm involves a single pass through the subdivision hierarchy, locating the test point at each level. Let p denote an arbitrary ...
[35]
Geometric range searching | ACM Computing Surveys
In geometric range searching, algorithmic problems of the following type are considered. Given an n-point set P in the plane, build a data structure.
[36]
[PDF] Geometric Range Searching and Its Relatives
We describe, in Section 2, di erent models of computation that have been used to prove upper and lower bounds on the performance of data structures. Next, in ...
[37]
[PDF] Lecture 8b: Nearest neighbors and Voronoi diagrams
Voronoi edges that meet at that vertex, remove the beach line curves that were between those edges, and start a new Voronoi edge between the beach line curves ...
[38]
A Unified Approach to Dynamic Point Location, Ray shooting, and ...
We describe a new technique for dynamically maintaining the trapezoidal decomposition of a connected planar map M with n vertices and apply it to the ...
[39]
[PDF] CMSC 754: Lecture 9 Trapezoidal Maps and Planar Point Location
The objective is to answer vertical ray-shooting queries, which means, given a query point q, what line segment si (if any) lies immediately below the query ...Missing: geometry | Show results with:geometry
[40]
[PDF] Amortised Analysis of Dynamic Data Structures
Mar 31, 2023 · Amortised analysis in dynamic data structures allows for simpler algorithms by relaxing efficiency measures, enabling efficient queries and ...
[41]
[PDF] Dynamic Data Structures for Geometric Set Cover with Sublinear ...
Mar 14, 2021 · This paper presents a dynamic data structure for geometric set cover with sublinear update time, achieving O(n^2/3+δ) for 2D axis-aligned ...
[42]
[PDF] Adaptive Precision Floating-Point Arithmetic and Fast Robust ...
Oct 1, 1997 · This article presents two techniques for writing fast implementations of extended precision calculations like these, and demonstrates them with ...
[43]
[1712.04564] Approximate Convex Hull of Data Streams - arXiv
Dec 12, 2017 · Computing an \epsilon-hull is an important problem in computational geometry, machine learning, and approximation algorithms. In many real ...Missing: approximations | Show results with:approximations
[44]
[PDF] Applications of Random Sampling in Computational Geometry, II
We give a randomized reduction from the diameter problem to the spherical intersection problem, resulting in a Las. Vegas algorithm for the diameter requiring O ...
[45]
Interval arithmetic yields efficient dynamic filters for computational ...
Apr 15, 2001 · We show that interval techniques can be used to speed up the exact evaluation of geometric predicates and describe an efficient implementation ...
[46]
[PDF] Least squares fitting of circles
Here we study the least squares fit (LSF) of circular arcs to incomplete scattered data. We analyze theoretical aspects of the problem and reveal the cause of ...
[47]
[PDF] Splines and Geometric Modeling - Purdue e-Pubs
The idea is to take a univariate interpolation scheme, apply it to all curves g(u, vd and g(Ui, v), add the resulting surfaces, and subtract the tensor product ...
[48]
On the Enduring Appeal of Least-Squares Fitting in Computational ...
For instance, for an unconstrained least-squares circle fit (considered in 2D) the average residual must be zero. If it is not, the fit is not the least-squares ...
[49]
[PDF] Geometric Computing with CGAL and LEDA - MPI-INF
LEDA provides an exact geometry kernel for rational computations. In- ternally, it uses floating-point filters [10,15] to speed up exact computation. With ...
[50]
Robustness Issues - CGAL 6.1 - Manual
The source of the robustness problem is that the default hardware-supported arithmetic does not really fulfill the requirements of the algorithm.Missing: multiprecision | Show results with:multiprecision
[51]
[PDF] On the Design of CGAL, the Computational Geometry Algorithms ...
May 24, 2006 · Algorithms in Cgal should be able to handle special cases and degeneracies. If this is expensive, additional versions are possible, which are ...
[52]
Controlled perturbation for Delaunay triangulations
Most geometric algorithms are idealistic in the sense that they are designed for the Real-RAM model of computation and for inputs in general position.
[53]
[PDF] The Power of Geometric Duality - cs.Princeton
The purpose of this paper is to use the concept of duality to study a number of problems involving points in the plane. In Section 2, we describe an optimal.
[54]
https://dl.acm.org/doi/10.5555/1070432.1070582
[55]
[PDF] Divide and Conquer in Multidimensional Space - Michael I. Shamos
We will present a divide-and-conquer algorithm for the closest-pair problem in the plane, generalize it to k-space, and extend the method to other closest-point ...
[56]
A simple and fast incremental randomized algorithm for computing ...
This paper presents a very simple incremental randomized algorithm for computing the trapezoidal decomposition induced by a set S of n line segments in the ...
[57]
[PDF] Efficient Algorithms for Geometric Optimization
Apr 1, 1998 · This technique, now known as decimation or prune-and- search, was later refined and extended by Dyer [99], Clarkson [68], and others. The tech-.
[58]
Multidimensional binary search trees used for associative searching
This paper presents a new type of data structure for associative searching, called the multidimensional bi- nary search tree or k-d tree, which is defined in ...
[59]
[PDF] QTree-ACTAInfo74.pdf - University of South Florida
3). This paper will discuss a generalization of the binary tree for the treatment of data with inherently two-dimensional structure. One clear ...Missing: original | Show results with:original
[60]
[PDF] Multidimensional Binary Search Trees in Database
It is easy to answer a range query in a k-d tree; Bentley. [1975] describes an algorithm for range searching similar to the partial-match searching algorithm ...
[61]
[PDF] Maintenance of Configurations in the Plane - UC Irvine
Mar 2, 1981 · MARK H.OVERMARS ANDJAN VAN LEEUWEN. 5. APPLICATIONS OF THE DYNAMIC CONVEX HULL ALGORITHM. There are numerous problems which can be solved by ...
[62]
[PDF] A Subdivision Algorithm for Computer Display of Curved Surfaces
A method for creating shaded pictures of curved surfaces is presented in this thesis. A motivation for the method is that we wish to produce high quality.
[63]
[PDF] On NURBS: a survey - IEEE Computer Graphics and Applications
I racking down the roots of NURBS as used in CAD and graphics is not easy. However. if we consider the two major ingredients of NURBS-ratio- nal and B ...
[64]
[PDF] Bounding Volume Hierarchies for Collision Detection - IntechOpen
Mar 30, 2012 · Bounding-. Volume Hierarchies (BVH) is the most fashionable approach used by researchers to perform collision checking. It represents the object ...Missing: seminal | Show results with:seminal
[65]
[PDF] Delaunay Refinement Mesh Generation
May 18, 1997 · Delaunay refinement is a technique for generating unstructured meshes of triangles or tetrahedra suitable for use in the finite element method ...
[66]
ARB_tessellation_shader - Khronos Registry
Section 7.1 of the OpenGL Shading Language Specification describes the built-in variable array gl_in[] available as input to a tessellation control shader.
[67]
Tessellation Stages - Win32 apps - Microsoft Learn
Sep 16, 2020 · The three tessellation stages are: Hull-Shader, which produces a geometry patch; Tessellator, which creates smaller objects; and Domain-Shader, ...
[68]
https://registry.khronos.org/OpenGL/extensions/ARB/ARB_tessellation_shader.txt
[69]
[PDF] Probabilistic Roadmaps for Path Planning in High-Dimensional ...
Kavraki, Petr Švestka, Jean-Claude Latombe, and Mark H. Overmars. Abstract— A new motion planning method for robots in static workspaces is presented. This ...
[70]
[PDF] Rapidly-Exploring Random Trees: A New Tool for Path Planning
We introduce the concept of a Rapidly-exploring Ran- dom Tree (RRT) as a randomized data structure that is designed for a broad class of path planning problems.
[71]
A generic solution to polygon clipping | Communications of the ACM
An algorithm for polygon clipping, and for determining polygon intersections and unions. This paper introduces a universal algorithm for polygon clipping ...Missing: original | Show results with:original
[72]
[PDF] A method for registration of 3-D shapes
CONCLUSIONS. The iterative closest point (ICP) algorithm is able to register a data shape with Np points to a model shape with Nx primitives. The model shape ...
[73]
New methods for computing visibility graphs - ACM Digital Library
The visibility graph GS of S is the graph that has the endpoints of the segments in S as nodes and in which two nodes are adjacent whenever they can “see” each ...Missing: seminal | Show results with:seminal<|separator|>
[74]
Robot Path Planning Using Generalized Voronoi Diagrams.
In this page, I give a brief overview of my work on the development of an efficient and robust algorithm for computing safe paths for a mobile robot.
[75]
[PDF] Parallel Computational Geometry - cs.Princeton
By symmetry, it is sufficient to show how to compute the upper chain in O(log(n)) time. First sort. S according to the x-coordinate of the points, using O(log(n)) ...
[76]
[PDF] Approximate Range Searching in Higher Dimension ∗ - cs.Princeton
Applying standard dimensionality reduction techniques, we show how to perform approximate range searching in higher dimension while avoiding the curse of ...Missing: simplex | Show results with:simplex
[77]
[PDF] Applications of Random Sampling in Computational Geometry, II
Abstract. We use random sampling for several new geometric algorithms. The algorithms are “Las Vegas,” and their expected bounds are with respect.
[78]
Applications of random sampling in computational geometry, II
Oct 1, 1989 · K. L. Clarkson and P. W. Shor. Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental. InProceedings of ...
[79]
https://www.cs.princeton.edu/~chazelle/pubs/cgta06.pdf
[80]
[PDF] Topological Persistence and Simplification
We classify a topological change that happens during growth as either a feature or noise depend- ing on its life-time or persistence within the filtration. We.
[81]
[PDF] On Range Searching with Semialgebraic Sets II∗
May 30, 2013 · As is typical in computational geometry, we will use the real RAM model of computation, where we can compute exactly with arbitrary real ...
[82]
Closest Pair Problems in Very High Dimensions - ResearchGate
Aug 7, 2025 · The problem of finding the closest pair among a collection of points in Âd\Re^d is a well-known problem.
[83]
[PDF] Computational Geometry in High-Dimensional Spaces
These data structures are typically efficient in 2D or 3D but suffer from hidden constant factors in the dimension d [10].
[84]
Persistent Homology in Data Science - SpringerLink
Jan 5, 2021 · In order to illustrate the versatility of TDA and persistent homology we discuss three domains of applications, namely the analysis of signals ...
[85]
Topological data analysis approach to time series and shape ...
Jun 17, 2025 · This study applied topological data analysis (TDA) tools, particularly persistent homology (PH), to analyze the time series and phase portrait ...
[86]
Graph Neural Networks in Point Clouds: A Survey - MDPI
This paper provides a comprehensive review of GNNs and graph-based methods in point cloud applications, adopting a task-oriented perspective to analyze this ...
[87]
Quantum K-Nearest Neighbors: Utilizing QRAM and SWAP-Test ...
It incorporates Grover's algorithm and the quantum SWAP-Test to identify similar states and determine the nearest neighbors with high probability, achieving O m ...
[88]
Turning Big Data Into Tiny Data: Coresets for Unsupervised ...
It allows us to turn our methods into streaming or distributed algorithms using standard approaches. For problems such as k -means and subspace approximation ...
[89]
[PDF] Dynamic Streaming Algorithms for Geometric Independent Set
The paper presents a space-efficient, dynamic streaming algorithm for computing a constant-factor approximation of the maximum independent set size of n axis- ...
[90]
Cable Connection Optimization for Heterogeneous Offshore Wind ...
Voronoi diagram of a multiple wind turbine types offshore wind farms. In Figure 3, there is a wind farm with 1 OS and 5 WTs (totally 2 types of WTs). It can be ...