Hubbry Logo
Computational geometryComputational geometryMain
Open search
Computational geometry
Community hub
Computational geometry
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Computational geometry
Computational geometry
Computational geometry
View on Wikipedia
from Wikipedia
Geometry
Stereographic projection from the top of a sphere onto a plane beneath it
Projecting a sphere to a plane
Branches
  • Concepts
  • Features
Dimension
Zero-dimensional
One-dimensional
Two-dimensional
Triangle
Quadrilateral
Circle
Three-dimensional
Polyhedron
Solid of revolution
Four-/other-dimensional
Geometers
by name
by period
BCE
1–1400s
1400s–1700s
1700s–1900s
Present day

Computational geometry is a branch of computer science devoted to the study of algorithms that can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O(n2) and O(n log n) may be the difference between days and seconds of computation.

The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer-aided design and manufacturing (CAD/CAM), but many problems in computational geometry are classical in nature, and may come from mathematical visualization.

Other important applications of computational geometry include robotics (motion planning and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated circuit design (IC geometry design and verification), computer-aided engineering (CAE) (mesh generation), and computer vision (3D reconstruction).

The main branches of computational geometry are:

  • Combinatorial computational geometry, also called algorithmic geometry, which deals with geometric objects as discrete entities. A groundlaying book in the subject by Preparata and Shamos dates the first use of the term "computational geometry" in this sense by 1975.[1]
  • Numerical computational geometry, also called machine geometry, computer-aided geometric design (CAGD), or geometric modeling, which deals primarily with representing real-world objects in forms suitable for computer computations in CAD/CAM systems. This branch may be seen as a further development of descriptive geometry and is often considered a branch of computer graphics or CAD. The term "computational geometry" in this meaning has been in use since 1971.[2]

Although most algorithms of computational geometry have been developed (and are being developed) for electronic computers, some algorithms were developed for unconventional computers (e.g. optical computers [3])

Combinatorial computational geometry

[edit]

The primary goal of research in combinatorial computational geometry is to develop efficient algorithms and data structures for solving problems stated in terms of basic geometrical objects: points, line segments, polygons, polyhedra, etc.

Some of these problems seem so simple that they were not regarded as problems at all until the advent of computers. Consider, for example, the closest pair problem:

  • Given n points in the plane, find the two with the smallest distance from each other.

One could compute the distances between all the pairs of points, of which there are n(n − 1)/2, then pick the pair with the smallest distance. This brute-force algorithm takes O(n2) time; i.e. its execution time is proportional to the square of the number of points. A classic result in computational geometry was the formulation of an algorithm that takes O(n log n). Randomized algorithms that take O(n) expected time,[4] as well as a deterministic algorithm that takes O(n log log n) time,[5] have also been discovered.

Problem classes

[edit]

The core problems in computational geometry may be classified in different ways, according to various criteria. The following general classes may be distinguished.

Static problem

[edit]

In the problems of this category, some input is given and the corresponding output needs to be constructed or found. Some fundamental problems of this type are:

The computational complexity for this class of problems is estimated by the time and space (computer memory) required to solve a given problem instance.

Geometric query problems

[edit]
See also: Spatial query

In geometric query problems, commonly known as geometric search problems, the input consists of two parts: the search space part and the query part, which varies over the problem instances. The search space typically needs to be preprocessed, in a way that multiple queries can be answered efficiently.

Some fundamental geometric query problems are:

  • Range searching: Preprocess a set of points, in order to efficiently count the number of points inside a query region.
  • Point location problem: Given a partitioning of the space into cells, produce a data structure that efficiently tells in which cell a query point is located.
  • Nearest neighbor: Preprocess a set of points, in order to efficiently find which point is closest to a query point.
  • Ray tracing: Given a set of objects in space, produce a data structure that efficiently tells which object a query ray intersects first.

If the search space is fixed, the computational complexity for this class of problems is usually estimated by:

  • the time and space required to construct the data structure to be searched in
  • the time (and sometimes an extra space) to answer queries.

For the case when the search space is allowed to vary, see § Dynamic problems.

Dynamic problems

[edit]

Yet another major class is the dynamic problems, in which the goal is to find an efficient algorithm for finding a solution repeatedly after each incremental modification of the input data (addition or deletion input geometric elements). Algorithms for problems of this type typically involve dynamic data structures. Any of the computational geometric problems may be converted into a dynamic one, at the cost of increased processing time. For example, the range searching problem may be converted into the dynamic range searching problem by providing for addition and/or deletion of the points. The dynamic convex hull problem is to keep track of the convex hull, e.g., for the dynamically changing set of points, i.e., while the input points are inserted or deleted.

The computational complexity for this class of problems is estimated by:

  • the time and space required to construct the data structure to be searched in
  • the time and space to modify the searched data structure after an incremental change in the search space
  • the time (and sometimes an extra space) to answer a query.

Variations

[edit]

Some problems may be treated as belonging to either of the categories, depending on the context. For example, consider the following problem.

In many applications this problem is treated as a single-shot one, i.e., belonging to the first class. For example, in many applications of computer graphics a common problem is to find which area on the screen is clicked by a pointer. However, in some applications, the polygon in question is invariant, while the point represents a query. For example, the input polygon may represent a border of a country and a point is a position of an aircraft, and the problem is to determine whether the aircraft violated the border. Finally, in the previously mentioned example of computer graphics, in CAD applications the changing input data are often stored in dynamic data structures, which may be exploited to speed-up the point-in-polygon queries.

In some contexts of query problems there are reasonable expectations on the sequence of the queries, which may be exploited either for efficient data structures or for tighter computational complexity estimates. For example, in some cases it is important to know the worst case for the total time for the whole sequence of N queries, rather than for a single query. See also Amortized analysis.

Numerical computational geometry

[edit]
Main article: computer-aided geometric design

This branch is also known as geometric modelling and computer-aided geometric design (CAGD).

Core problems are curve and surface modelling and representation.

The most important instruments here are parametric curves and parametric surfaces, such as Bézier curves, spline curves and surfaces. An important non-parametric approach is the level-set method.

Application areas of computational geometry include shipbuilding, aircraft, and automotive industries.

List of algorithms

[edit]
This section is an excerpt from List of algorithms § Geometry.[edit]

See also

[edit]

References

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Computational geometry

View on Grokipedia
from Grokipedia
Computational geometry is a branch of 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. It emerged as a distinct in the early , with the term coined by Michael Ian Shamos in 1973 during his work at on problems like computing Voronoi diagrams and closest pairs of points. 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. 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. These algorithms emphasize exact computations with real numbers and asymptotic worst-case analysis, though practical implementations must address issues like numerical precision. Applications span diverse areas, including for rendering and , robotics for and , geographic information systems (GIS) for spatial queries and mapping, computer-aided design (CAD/CAM) for solid modeling, and scientific computing fields like . More recent advancements incorporate approximation algorithms for high-dimensional data and integration with for tasks like shape analysis.

Overview

Definition and Scope

Computational geometry is a branch of and dedicated to the design, analysis, and implementation of efficient algorithms for solving geometric problems involving points, lines, polygons, and . 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. 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 to model continuous real-world geometries with inherent precision limitations. Combinatorial approaches emphasize worst-case guarantees and topological properties, while numerical methods prioritize practical approximations for curved or high-precision inputs. The scope of computational geometry centers on achieving efficiency in time and 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. This emphasis extends to both 2D problems, which form the foundational core due to their tractability, and 3D extensions, which introduce added in dimensionality but share similar efficiency goals. 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. These connections underpin applications in areas including for rendering and for path planning.

History

The roots of computational geometry lie in mathematics, particularly in 's Elements (c. ), which systematized geometric constructions as step-by-step procedures using a and , laying the groundwork for algorithmic approaches to geometric problems such as formation and inscriptions. These methods emphasized exact constructions from basic primitives, influencing later computational interpretations of geometry as a discrete, verifiable process. In the 19th and early 20th centuries, precursors emerged through the integration of and numerical methods, with ' (1637) enabling algebraic representations of geometric objects suitable for computation. By the mid-20th century, applications in 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 . The modern discipline of computational geometry was formally established in the , 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. Shamos' 1978 Ph.D. further solidified these foundations, demonstrating efficient O(n log n) methods for proximity and . 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, detection, and . The 1980s and 1990s marked rapid institutional growth, with the first Symposium on Computational Geometry (SoCG) held in in , fostering annual exchanges on algorithmic advances. This was followed by the launch of the journal Computational Geometry: Theory and Applications in by , providing a dedicated venue for theoretical and applied research. 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.

Fundamental Concepts

Geometric Primitives

In computational geometry, geometric serve as the foundational building blocks for representing and manipulating spatial data, typically in Euclidean spaces of low such as R2\mathbb{R}^2 or R3\mathbb{R}^3. These include points, lines, line segments, polygons, and circles, each defined through mathematical representations that facilitate algorithmic processing. Higher-level , such as convex sets and simplices, extend these basics by incorporating convexity properties essential for optimization and tasks. Points are the simplest primitives, denoted as coordinate tuples in Rd\mathbb{R}^d. In two dimensions, a point pp is represented as (px,py)(p_x, p_y), where pxp_x and pyp_y are real numbers specifying positions along orthogonal axes. In three dimensions, points extend to (px,py,pz)(p_x, p_y, p_z). The Euclidean distance between two points pp and qq in Rd\mathbb{R}^d, which measures the straight-line separation, is given by the formula d(p,q)=∑i=1d(pi−qi)2,d(p, q) = \sqrt{\sum_{i=1}^d (p_i - q_i)^2},
Add your contribution
Related Hubs
User Avatar
No comments yet.