1. Definition and Basic Notation

A polygonal chain is a sequence of points \(v_0, v_1, \dots, v_n\) together with the straight line segments connecting consecutive points, \([v_i, v_{i+1}]\) for \(i=0,\dots,n-1\). The segments form a connected geometric object because each pair of successive segments meets at a shared vertex \(v_{i+1}\).

1.1 Vertices, segments, and ordering

The points \(v_i\) are called vertices, and the connecting segments are edges of the chain. The index order \(v_0 \to v_1 \to \cdots \to v_n\) specifies the traversal direction, which matters for quantities such as turning angle and for computational tasks that depend on orientation.

Unless otherwise stated, vertices are taken to be distinct from their immediate neighbors; however, non-adjacent vertices may coincide in degenerate cases unless excluded by a “simplicity” condition.

1.2 Open vs. closed polygonal chains

An open polygonal chain has distinct endpoints \(v_0 \neq v_n\). A closed polygonal chain has endpoints coincident, typically written as \(v_n=v_0\), and is understood to form a loop. For closed chains, cyclic order is important: rotating the starting index does not change the underlying geometric loop.

1.3 Geometric embedding (plane vs. space)

Polygonal chains may lie in the plane \(\mathbb{R}^2\) (2D) or in three-dimensional space \(\mathbb{R}^3\) (3D). Most definitions extend directly: vertices are points in the ambient space and segments are straight interpolations between them. In 3D, turning behavior is often analyzed using local angles formed by consecutive edges, with additional care for how “direction change” is measured.

1.4 Length, polyline metric, and parameterization

The length of a polygonal chain is the sum of Euclidean lengths of its segments: \[

L=\sum_{i=0}^{n-1}\|v_{i+1}-v_i\|.

\] This “polyline metric” is a discrete surrogate for the arc length of smooth curves. A chain can be parameterized continuously along its segments: one common approach maps a parameter interval to each segment proportionally to its length, yielding a piecewise-linear parameterization that supports distance and approximation analyses.

2. Structural Properties

Structural properties describe how the chain sits in space and how its local geometry behaves at vertices and along segments.

2.1 Simplicity and self-intersection

A polygonal chain is called simple if it does not cross itself; more precisely, non-adjacent segments do not intersect except possibly at shared endpoints that are consistent with adjacency. If intersections occur between non-consecutive edges, the chain is self-intersecting. For computational tasks, distinguishing these cases is fundamental because intersections can change downstream results such as distance computations and visibility queries.

2.2 Collinearity and degenerate vertices

A vertex \(v_i\) (for \(1 \le i \le n-1\)) is collinear if the three consecutive points \(v_{i-1}, v_i, v_{i+1}\) lie on a single line. In such a case, the chain does not “turn” at \(v_i\). Degenerate situations also include repeated consecutive points (leading to zero-length segments) or numerical near-degeneracies, which can destabilize geometric predicates if not handled carefully.

2.3 Turning angles and local direction changes

At each internal vertex, one can define a turning angle that quantifies the change in direction from edge \([v_{i-1},v_i]\) to edge \([v_i,v_{i+1}]\). In the plane, an oriented turning angle can be defined using the sign of a 2D cross product; in 3D, turning is typically characterized using the angle between edge vectors, optionally augmented by an orientation convention. These local angles collectively describe the chain’s global “shape tendency.”

2.4 Vertex degree and endpoint behavior

Although polygonal chains are not graphs by default, they can be interpreted as graph walks: each internal vertex has two incident chain edges, while endpoints have one. This “degree” perspective becomes useful when the chain is extracted from a larger graph structure (e.g., a navigation network) or when multiple chains share vertices in a geometric data model. Endpoint behavior often affects metrics like total turning, especially for open chains where the chain’s direction does not loop back to itself.

3. Special Classes of Polygonal Chains

Some families of polygonal chains are singled out because their structure yields efficient algorithms or clean theoretical properties.

3.1 Monotone polygonal chains

A polygonal chain is monotone with respect to an axis direction if its progression never reverses that coordinate. For instance, in \(\mathbb{R}^2\), a chain can be x-monotone if the x-coordinates of vertices are non-decreasing (or non-increasing) along the order. Monotonicity simplifies visibility and intersection tests because the chain intersects certain vertical lines in a controlled manner.

3.2 Convex and reflex vertices

For planar chains, a vertex is often classified as convex or reflex based on the internal turning direction relative to the local polygonal “turn.” Intuitively, a convex vertex bends the chain in one rotational sense, while a reflex vertex bends in the opposite sense, potentially generating “indentations.” This classification underlies reasoning about simple polygons, polygonal approximations of smooth convex curves, and constrained simplification.

3.3 Orthogonal (axis-aligned) polygonal chains

An orthogonal polygonal chain consists of segments aligned with coordinate axes (e.g., horizontal and vertical segments in the plane). Such chains arise in grid-based routing, VLSI layout representations, and certain types of path sketches. Axis alignment makes many geometric predicates discrete: intersection, distance-to-segment, and turn detection can exploit Manhattan-style structure, although Euclidean distance remains relevant in general measurements.

3.4 Polygonal chains with constraints (e.g., bounded curvature in discrete form)

Some applications impose constraints on how sharply a chain may bend. In discrete settings, “curvature” is approximated by turning angles distributed across vertices or by variations in edge direction across short spans. Bounded curvature in discrete form can be used to model physically plausible motion, reduce unrealistic zig-zagging in approximations, or ensure that smoothing algorithms do not introduce excessive directional changes.

4. Measures and Derived Quantities

Beyond total length, polygonal chains support aggregate quantities that summarize geometry and enable comparison.

4.1 Perimeter-like length measures

For closed chains that represent loops, the sum of edge lengths functions as a perimeter-like measure. For open chains, the same sum describes travel distance along the polyline rather than a closed boundary measure. In either case, length-based comparisons are common for ranking paths, evaluating compression, and measuring approximation error.

4.2 Total turning angle

Total turning angle aggregates the vertex turning angles across the chain. For simple closed planar chains, the total turning is closely related to winding and the traversal of the tangent direction; it becomes a diagnostic quantity for whether the chain behaves like a well-formed loop. For open chains, total turning provides a measure of how much the path “wiggles” overall, even when endpoints do not close the direction.

When a closed planar polygonal chain forms a simple polygon (or is interpreted as such), one can define area using discrete versions of the shoelace formula. For self-intersecting chains, area definitions can vary (e.g., signed area vs. geometric area), but discrete formulations still enable computation and facilitate comparisons in applications such as shape approximation and silhouette analysis.

Discrete curvature assigns a curvature value to vertices (or intervals around them) based on turning behavior and local geometry. Common summaries include curvature concentrated at vertices, curvature integrated over edge neighborhoods, or curvature distributions used in regularization objectives. These discrete curvature quantities support tasks such as smoothing, detecting corners, and differentiating “nearly straight” regions from genuinely curved ones.

5. Transformations and Equivalences

Polygonal chains are often manipulated without changing the geometric essence of interest.

5.1 Rigid motions and invariance of properties

Rigid motions—translations and rotations (and reflections, depending on conventions)—preserve distances and angles. As a result, properties based on edge lengths, turning angles, and intersections are invariant under rigid transformations. This invariance is useful for canonicalization: chains can be aligned to a standard orientation for comparison or for robust detection.

5.2 Simplification via vertex removal

Simplification reduces the number of vertices while aiming to preserve shape to within tolerance. Vertex removal typically merges consecutive segments by discarding intermediate points and replacing multiple edges with a single straight segment. Good simplification strategies control the geometric error, such as maximum deviation from the original polyline or errors in cumulative turning.

5.3 Subdivision (refining segments by adding vertices)

Subdivision refines a chain by adding vertices along segments. If new vertices lie exactly on existing segments, they do not change the polyline’s geometric locus, though they affect discrete representations of turning and curvature if those are computed per vertex. Subdivision can improve numerical stability in algorithms that need finer sampling, or prepare a chain for smoothing procedures.

5.4 Reparameterization and vertex relabeling

Reparameterization changes the parameter along the chain but not its geometric embedding. Vertex relabeling changes indices while preserving order and structure; for closed chains, relabeling may correspond to a cyclic shift of the starting index. For algorithms that depend on correspondence between points across different chains, maintaining consistent vertex order is essential even when the parameterization is altered.

6. Computational Aspects

Computational geometry uses polygonal chains as primitive objects because operations on them are comparatively tractable.

6.1 Detecting intersections and simplicity checks

Intersection detection involves testing segment pairs for geometric intersection, excluding adjacent segments that share a vertex. Naive approaches compare all segment pairs, while efficient methods employ spatial indexing or sweep-line techniques. For simplicity checks, the goal is to determine whether any non-adjacent segments intersect in an impermissible way, with careful handling of collinear overlaps and touching endpoints.

6.2 Point-to-polyline distance computations

Distance from a point to a polyline is typically defined as the minimum Euclidean distance to any constituent segment. Computationally, this reduces to computing point-to-segment distances and taking the minimum. These distance functions are used in fitting, snapping trajectories to paths, and evaluating error in approximation or compression tasks.

6.3 Polyline approximation and error bounds

Approximation replaces a detailed chain with a simpler one (fewer vertices) while bounding the deviation. Error can be measured as maximum perpendicular distance to the original polyline, Hausdorff distance under certain assumptions, or integrated error along the chain. Many algorithms are dynamic-programming or greedy in nature, balancing runtime against approximation quality.

6.4 Hausdorff/Fréchet-like discrete comparisons overview level

Comparing shapes often requires robust distance notions between polylines or between sets of points. Discrete Hausdorff distances quantify the worst-case proximity between point sets derived from chains, while Fréchet-like measures account for the order of traversal along curves. In the polygonal setting, these comparisons can be approximated or computed using discrete dynamic programming, though exact computation may be costly depending on the chosen metric and sampling strategy.

7. Algorithmic Applications in Discrete Geometry

Polygonal chains serve as the core representation for many geometric algorithms because they bridge continuous geometry and discrete computation.

7.1 Path planning and routing polylines

In motion planning and routing, feasible paths are often represented as polylines derived from sampled waypoints, visibility graphs, or grid-based planning. The polyline provides a manipulable geometric object: segments can be checked for collisions, and local turning constraints can be enforced or approximated. The ordering of vertices directly encodes the travel sequence.

7.2 Collision detection with segments

Collision detection frequently reduces to checking intersections between moving objects and polygonal chain segments, or between two chains representing trajectories. Segment-level intersection and distance-to-segment queries are key primitives. For efficiency, systems commonly use bounding volume hierarchies or spatial hashing to avoid exhaustive pairwise checks.

7.3 Smoothing or regularization discrete variants

Smoothing aims to reduce sharp corners and noise while maintaining fidelity to the underlying path. Discrete methods might adjust vertex positions using local averaging, optimization objectives that penalize curvature proxies, or iterative projection schemes constrained by obstacle avoidance or endpoint conditions. Regularization is particularly important when chains are extracted from noisy measurements.

7.4 Data compression of geometric trajectories

A trajectory sampled over time can be encoded as a polygonal chain, where vertices correspond to recorded positions. Compression seeks to reduce storage and transmission cost by replacing many vertices with fewer while controlling error relative to the original. Approximation error bounds, corner preservation, and runtime constraints guide which simplification strategy is appropriate for a given application.