Chapter 45. Computational Geometry Connections

Computational geometry studies algorithms for geometric objects: points, line segments, polygons, polyhedra, subdivisions, and arrangements. Graph theory enters naturally because many geometric structures have vertices, edges, adjacency, paths, faces, and duality.

In graph theory, a graph often begins as an abstract pair

In computational geometry, the vertices are often points in Euclidean space, and edges are often straight-line segments. The graph is then constrained by geometry. Distances, crossings, angles, visibility, convexity, and embedding all become part of the problem.

45.1 From Graphs to Geometry

A geometric graph is a graph whose vertices are placed as points and whose edges are drawn as straight-line segments. This gives the graph a metric structure.

If a vertex $v$ is placed at a point

then an edge $uv$ has Euclidean length

Thus an abstract graph becomes a geometric object. We can now ask questions that have no meaning in a purely abstract graph.

Computational geometry supplies algorithms for answering such questions efficiently.

45.2 Planar Straight-Line Graphs

A planar straight-line graph is a planar embedding in which every edge is drawn as a line segment. It is also called a straight-line plane graph.

Such graphs are common in computational geometry because they describe polygonal subdivisions of the plane. A planar straight-line graph can represent boundaries of polygons, triangulations, road maps, mesh structures, and geographic maps.

Every simple planar graph has a crossing-free straight-line drawing. This is Fary’s theorem. It allows one to pass from topological planarity to straight-line geometry for simple planar graphs.

The distinction is important:

A planar straight-line graph is both a plane graph and a geometric graph.

45.3 Segment Intersection

One of the basic algorithmic problems is segment intersection.

Given a set of line segments in the plane, determine whether any two intersect, or compute all intersection points.

This problem is directly graph-theoretic. If each segment is treated as a vertex and intersections define adjacency, then the result is an intersection graph. If the segments are edges in a geometric graph, then intersections determine whether the drawing is planar.

Segment intersection is used in:

In planar graph algorithms, detecting and avoiding crossings is a basic operation.

45.4 Triangulations

A triangulation divides a geometric region or point set into triangles.

For a point set in the plane, a triangulation is a maximal planar straight-line graph on that point set. No further straight edge can be added without creating a crossing.

If the point set has $n$ points and $h$ points on its convex hull, then any triangulation has

edges and

triangles.

These formulas follow from Euler’s formula applied to the planar straight-line graph formed by the triangulation.

Triangulations are central in computational geometry because they convert an irregular point set into a structured mesh.

45.5 Delaunay Triangulations

The Delaunay triangulation is a special triangulation of a point set. In the usual nondegenerate case, no point lies inside the circumcircle of any triangle in the triangulation.

The Delaunay triangulation is closely related to the Voronoi diagram. The Voronoi diagram partitions the plane into cells, one for each site. Two sites are joined by a Delaunay edge when their Voronoi cells share a boundary. Thus the Delaunay triangulation is the graph dual of the Voronoi diagram under standard nondegeneracy assumptions.

This is a direct instance of planar duality.

Delaunay triangulations are used in mesh generation, interpolation, nearest-neighbor search, and scientific computing.

45.6 Voronoi Diagrams

Given a finite set of sites in the plane, the Voronoi diagram partitions the plane into regions according to nearest site.

The cell of a site $p_i$ is

Each cell contains all points at least as close to $p_i$ as to any other site.

The adjacency graph of Voronoi cells is the Delaunay graph. Thus graph theory appears twice: first in the cell adjacency structure, and second in the dual triangulation.

Voronoi diagrams are used in facility location, spatial indexing, robotics, graphics, and computational biology.

45.7 Convex Hulls

The convex hull of a finite point set is the smallest convex polygon containing all the points.

Its boundary forms a cycle graph. The vertices of this cycle are the extreme points of the set, listed in circular order.

Convex hull algorithms therefore produce both a geometric object and a graph structure:

Convex hulls are often the first step in geometric algorithms. They also define the outer face of triangulations of point sets.

45.8 Visibility Graphs

A visibility graph records which points can see each other in the presence of obstacles.

Given points and polygonal obstacles, two points are adjacent if the segment between them does not pass through the interior of an obstacle. Visibility graphs are used in computational geometry and robot motion planning, especially for shortest paths among polygonal obstacles.

The graph transforms a continuous geometric path problem into a discrete shortest-path problem.

In a polygonal environment, shortest paths often bend only at obstacle vertices. This makes a graph representation effective.

45.9 Arrangements

An arrangement is the subdivision of the plane induced by a set of geometric objects, such as lines, segments, or curves.

For example, a set of lines divides the plane into vertices, edges, and faces. These form an embedded planar graph.

Arrangements are important because many geometric problems can be reduced to searching or traversing the cells of such subdivisions.

The arrangement viewpoint turns geometry into a planar graph with additional coordinates.

45.10 Planar Subdivisions

A planar subdivision partitions the plane into vertices, edges, and faces. It may represent a map, mesh, polygon decomposition, Voronoi diagram, or arrangement.

A planar straight-line graph is a common representation of a planar subdivision in computational geometry. In this setting, faces are polygonal regions.

Algorithms on planar subdivisions include:

These problems rely on the same vertex-edge-face structure studied in planar graph theory.

45.11 Proximity Graphs

A proximity graph connects points that are close under some geometric rule.

Examples include nearest-neighbor graphs, unit disk graphs, Gabriel graphs, relative neighborhood graphs, and Delaunay graphs.

The main idea is that geometry determines adjacency.

These graphs are used in clustering, wireless networks, mesh generation, and spatial data analysis.

45.12 Euclidean Minimum Spanning Trees

Given points in the plane, the Euclidean minimum spanning tree connects all points with minimum total edge length.

It is a graph-theoretic optimization problem with geometric edge weights.

A useful fact is that the Euclidean minimum spanning tree is contained in the Delaunay triangulation. This means one can compute the Delaunay triangulation first, then run a graph minimum-spanning-tree algorithm on its edges rather than on all pairwise distances. Delaunay triangulations are commonly used this way in Euclidean network problems.

This illustrates a recurring pattern:

45.13 Meshes

A mesh is a geometric graph used to approximate a continuous shape or domain. In two dimensions, meshes are often made of triangles or quadrilaterals. In three dimensions, they may use tetrahedra or hexahedra.

Meshes are used in finite element methods, computer graphics, simulation, and geometric modeling.

Graph theory describes the connectivity of the mesh:

Computational geometry supplies algorithms to generate and improve meshes. Graph theory supplies traversal, coloring, partitioning, and adjacency algorithms.

45.14 Point Location

Point location asks:

Given a planar subdivision and a query point $q$, which face contains $q$?

This is a geometric search problem on an embedded graph. The subdivision may be a triangulation, Voronoi diagram, map, or arrangement.

Efficient point-location data structures preprocess the subdivision so that queries can be answered quickly.

In graph-theoretic terms, point location identifies the face of a plane graph that contains a geometric point.

45.15 Graph Drawing

Graph drawing studies how to place vertices and edges so that a graph is readable.

Computational geometry contributes methods for:

Planar graph drawing is especially close to computational geometry because embeddings, faces, coordinates, and crossings are all central.

45.16 Algorithmic Pattern

Many computational geometry problems follow the same pattern.

First, build a geometric structure. Second, interpret it as a graph. Third, run a graph algorithm.

This pattern explains why graph theory is a core tool in computational geometry.

45.17 Summary

Computational geometry studies algorithms for geometric objects, while graph theory studies discrete adjacency and incidence. The connection is direct because geometric structures naturally form graphs.

The main correspondences are:

The central method is to convert continuous geometry into a finite graph while preserving the structure needed for the problem. Once this conversion is made, graph algorithms can compute paths, trees, cuts, colorings, traversals, and decompositions.