1 Definition and Basic Properties

1.1 Polygonal chain terminology

A polygonal chain is a sequence of points \(p_0, p_1, \dots, p_n\) in the plane (or in higher dimensions) such that consecutive points are connected by line segments \(\overline{p_ip_{i+1}}\). The chain is often called open when it has distinct start and end vertices, and it is simple when it does not self-intersect except at shared endpoints. The terms vertex (the points \(p_i\)) and edge (the segments between consecutive vertices) are used to describe the chain’s structure.

1.2 Monotonicity in a chosen direction

Fix a direction in the plane, represented by an axis (e.g., the \(x\)-axis) or more generally by a nonzero vector \(d\). A chain is called monotone with respect to that direction if, when the chain is traversed from \(p_0\) to \(p_n\), the coordinate projected onto the direction changes in a single consistent manner—commonly defined as being non-decreasing or non-increasing. In the common \(x\)-monotone case, a chain is \(x\)-monotone if the \(x\)-coordinates along the traversal do not go backward: for indices \(i < j\), the projected values satisfy \(x(p_i) \le x(p_j)\) (non-decreasing) or \(x(p_i) \ge x(p_j)\) (non-increasing), with the sign convention chosen once for the chain.

More generally, projection onto a direction \(d\) uses a scalar quantity \(t(p)=p\cdot d\). The chain is monotone if \(t(p_i)\) is non-decreasing (or non-increasing) along the traversal.

1.3 Strict vs non-strict monotonicity

Monotonicity is often stated in either non-strict or strict form.

  • Non-strict monotonicity allows equal projected values at consecutive vertices (e.g., a horizontal segment for an \(x\)-monotone chain would have constant \(x\)). Formally, \(t(p_{i+1}) \ge t(p_i)\).
  • Strict monotonicity requires the projected values to change in the correct direction without staying constant, i.e., \(t(p_{i+1}) > t(p_i)\).

Which version is appropriate depends on the intended downstream operations. Algorithms that sweep along the monotone coordinate often prefer non-strict forms because they tolerate collinearities or segments aligned with the direction.

1.4 Vertex and edge behavior (endpoints, collinearity)

Even when vertex projections are monotone, edges can introduce subtlety if degeneracies are present. For example:

  • At endpoints, the monotonicity condition typically applies along the chain from start to end, so both endpoints are included in the ordered sequence.
  • For collinear runs, multiple consecutive edges may keep the projection constant (non-strict) or change smoothly (strict). Degenerate cases such as repeated points can produce zero-length edges, which do not violate monotonicity in projection-based formulations but may affect robustness in practice.
  • Vertical or horizontal edges relative to the chosen axis affect whether strict monotonicity is possible and whether different vertices share the same projected value.

A careful definition usually treats vertices and edges consistently under the same projection rule, ensuring that if vertex projections behave monotonically, then the chain’s overall traversal does too in the intended sense.

1.5 Equivalent characterizations

For planar chains and standard coordinate directions, multiple equivalent viewpoints are common:

  1. Order of projected coordinates: The scalar projection \(t(p_i)\) is monotone along the vertex sequence.
  2. Support-line/side interpretation: For \(x\)-monotonicity, every vertical line intersects the chain in a connected set (possibly empty) when considering an appropriately constrained traversal, under additional assumptions such as simplicity and non-self-intersection.
  3. Single-crossing property (under simplicity): Under typical conditions (e.g., the chain is simple and not “doubling back”), each line orthogonal to the direction meets the chain at most once along the monotone sweep direction.

In practice, the easiest and most direct check is the first characterization (projection along vertices), while the others are useful for geometric reasoning and for linking monotonicity to intersection and visibility properties.

2 Types of Monotone Chains

2.1 x-monotone chains

A chain is \(x\)-monotone if its \(x\)-coordinate is monotone non-decreasing or non-increasing along the traversal. A common convention is non-decreasing \(x\). Under that convention, the chain “moves from left to right without reversing in \(x\).” This notion is central in polygon decomposition because many geometric algorithms use vertical sweeps.

2.2 y-monotone chains

Similarly, a chain is \(y\)-monotone if the \(y\)-coordinate along the vertex sequence is monotone in the chosen direction. This is the analogous concept for horizontal sweeps and is often interchangeable with \(x\)-monotonicity after rotating axes.

2.3 Monotone with respect to an arbitrary axis/direction vector

Using the dot-product projection \(t(p)=p\cdot d\), a chain is monotone with respect to direction \(d\) if \(t(p_i)\) is non-decreasing or non-increasing along the chain. This generalization allows monotonicity to align with a computation’s geometry (for example, a sweep direction chosen to simplify intersection patterns).

2.4 Lower vs upper monotone chains

When discussing polygons (especially in contexts like monotone polygon decomposition), one often distinguishes:

  • Upper chain: typically the chain that lies on the “top” boundary when traversing from leftmost to rightmost vertices.
  • Lower chain: the corresponding “bottom” boundary.

For an \(x\)-monotone polygon, the boundary can often be split into an upper and a lower \(x\)-monotone chain from the leftmost to the rightmost extreme points. The terms “upper” and “lower” depend on the embedding and on a chosen traversal convention.

2.5 Handling vertical or horizontal segments

Segments aligned with the chosen sweep direction can cause repeated projected values:

  • For \(x\)-monotonicity, a segment vertical to the \(x\)-axis has constant \(x\). This is compatible with non-strict monotonicity but prevents strict monotonicity.
  • For \(y\)-monotonicity, the analogous statement holds for horizontal segments.

Algorithms and definitions usually accommodate these cases by using the non-strict version unless strictness is explicitly required.

In robustness-focused implementations, vertical/horizontal segments are also treated carefully because they are often sources of division-by-zero errors in slope-based computations; projection-based monotonicity checks avoid many such pitfalls.

3 Testing Monotonicity

3.1 Naive check by coordinate ordering

A straightforward method tests monotonicity directly on vertex coordinates. For \(x\)-monotonicity (non-decreasing), verify: \[ x(p_{i+1}) \ge x(p_i)\quad \text{for all } i=0,\dots,n-1. \] If the chosen convention is non-increasing, use \(\le\) instead. For monotonicity with respect to a general direction \(d\), check: \[ p_{i+1}\cdot d \ge p_i\cdot d \quad \text{for all } i. \] This approach is simple, fast, and correct under the projection-based definition.

3.2 Edge-by-edge verification strategies

When implementations need to account for degeneracies or when definitions are stated in terms of intersection behavior, more geometric checks are used. A typical strategy is to ensure that each edge does not introduce a backward step relative to the direction. For projection-based monotonicity, the per-edge condition is implied by the vertex condition because along a straight segment the projection varies linearly between endpoint projections. However, if the chain has repeated vertices, nearly coincident points, or if strict monotonicity is desired, an edge-by-edge strategy may be used to explicitly detect constant-projection edges, non-advancing vertices, or invalid transitions.

3.3 Computational considerations (integer vs real coordinates)

With integer coordinates, comparisons of projected values can be performed exactly if the projection is represented as an integer dot product (or after scaling). With real coordinates, floating-point error may cause violations that are numerically tiny. In that setting, implementations often:

  • use an epsilon tolerance in comparisons, or
  • use exact arithmetic (e.g., rational representations) when feasible.

Choosing a tolerant comparison affects whether a chain is classified as monotone in ambiguous cases where projected values are “almost equal.”

3.4 Robustness and degeneracies (repeated vertices, collinear runs)

Degeneracies can be handled consistently by the definition:

  • Repeated vertices yield equal projection values and should not break non-strict monotonicity. They may be removed by simplification steps if desired.
  • Collinear runs aligned with the sweep direction produce constant projected values and are compatible with non-strict monotonicity.
  • Mixed cases (e.g., some edges with increasing projection and others with constant projection) are allowed so long as there is no decrease in projected values.

A practical robustness approach first applies simplification (optional) to remove zero-length edges, then checks monotonicity using stable comparisons.

3.5 Complexity analysis

If monotonicity is tested by scanning vertex projections, the time is linear in the number of vertices:

  • Time: \(O(n)\) comparisons for a chain with \(n+1\) vertices.
  • Space: \(O(1)\) additional space beyond storing the chain, if projections are computed on the fly.

More elaborate geometric checks (e.g., connected-intersection properties) can require additional bookkeeping, but for projection-defined monotonicity, the linear scan is sufficient.

4 Geometric Consequences and Constraints

4.1 Relationship to support lines and directionality

Monotonicity in a direction implies that the chain has an ordered relationship to lines orthogonal to that direction. Intuitively, as one moves along the chain parameter, the chain never “passes back” across the same orthogonal slice. This yields a kind of one-way traversability: supporting lines perpendicular to the direction encounter the chain in a consistent progression.

4.2 Bounds on crossings with vertical/horizontal lines

For \(x\)-monotone chains, vertical lines \(x=c\) intersect the chain in a controlled manner when the chain is simple and properly oriented. The chain does not create multiple “back-and-forth” occurrences in the same vertical slice. As a consequence, vertical sweeps can treat intersections in an ordered fashion, which is foundational for sweep-line algorithms.

4.3 Implications for polygonal representations

When the boundary of a polygon can be expressed as one or two monotone chains (upper and lower), the polygon representation becomes easier to process. Many operations—finding visibility, decomposing into simpler shapes, and triangulation—benefit from the reduced complexity of having boundaries that behave predictably under directional sweeps.

4.4 Visibility/occlusion intuition in monotone boundaries

In visibility terms, monotone boundaries tend to occlude objects consistently. For example, if a boundary is \(x\)-monotone, then moving in the sweep direction encounters the boundary at increasing \(x\) values without re-entering “earlier” slices. This supports reasoning that visible regions change in structured ways rather than irregularly oscillating due to turn-back behavior.

These are intuitive consequences; formal visibility algorithms still require explicit intersection tests, but monotonicity constrains the possible configurations.

5 Operations Involving Monotone Chains

5.1 Merging and concatenating monotone segments

Two chains can be concatenated while preserving monotonicity if their projected coordinate ranges align correctly and the join does not violate the direction order. For instance, concatenating two non-decreasing \(x\)-monotone chains is valid when the end \(x\)-coordinate of the first chain is less than or equal to the start \(x\)-coordinate of the second, and when the transition does not introduce a decrease across the join.

In practical settings, merging is also constrained by geometric consistency (e.g., shared endpoints and avoidance of self-intersections), but projection monotonicity is governed mainly by the coordinate order.

5.2 Splitting a chain into monotone subchains

If a chain fails global monotonicity, it can sometimes be partitioned into contiguous segments that are monotone. A typical approach locates indices where the projection switches from increasing to decreasing (or vice versa), then cuts the chain accordingly. This produces monotone subchains that can be handled by algorithms assuming monotonic structure.

When strictness is required, splits must also account for constant-projection runs to avoid “stalling” where progression is disallowed.

5.3 Simplifying (optional) without breaking monotonicity

Simplification may remove redundant vertices or zero-length edges while maintaining the projection order:

  • removing consecutive collinear vertices that do not change the projected trend,
  • contracting repeated points,
  • optionally simplifying within constant-projection segments.

Care is taken to ensure the remaining vertex sequence still satisfies the chosen inequality checks (e.g., non-decreasing).

5.4 Intersection and sweep-line friendliness

Monotonicity makes intersection handling more systematic for sweeps orthogonal to the monotone direction. As a sweep progresses, potential intersections with a monotone chain occur in an order consistent with the chain’s traversal parameter. This property reduces the need for complex backtracking and enables data structures that rely on sorted events.

While monotonicity does not eliminate intersections by itself, it makes their organization predictable.

6 Applications in Discrete Computational Geometry

6.1 Monotone polygon structures

A polygon is commonly described as monotone if its boundary can be decomposed into monotone chains with respect to a chosen axis (most often \(x\)). For an \(x\)-monotone polygon, any vertical line intersects the polygon in a single segment (possibly degenerate), yielding a strong structural constraint.

This structure supports efficient processing compared to arbitrary simple polygons.

6.2 Decomposition ideas using monotone boundaries

Many geometric pipelines decompose complex shapes into simpler components. Monotone boundaries serve as building blocks because monotone polygons can be partitioned further (e.g., into triangles or other pieces) using algorithms that assume a directional structure. Decomposition often proceeds by:

  1. converting boundaries into monotone chains,
  2. processing the monotone pieces independently,
  3. combining results.

6.3 Algorithmic simplifications from monotonicity

Monotonicity reduces degrees of freedom. For example, operations that depend on how a boundary intersects sweep lines can leverage sorted event order. Additionally:

  • adjacency relationships along the boundary align with sweep ordering,
  • candidate intersection pairs can be filtered more aggressively,
  • local decisions depend less on global geometry.

6.4 Typical subroutines that exploit monotone chains

Common subroutines where monotone chains appear include:

  • locating extreme points (for choosing split boundaries),
  • performing sweep-line intersection computations,
  • triangulating monotone polygons,
  • splitting a polygon at strategic diagonals to obtain monotone pieces.

In many implementations, monotonicity functions as an enabling condition that unlocks simpler computational logic.

7 Worked Examples and Visual Intuition

7.1 Example: verifying x-monotonicity step-by-step

Consider vertices \(p_0=(0,0), p_1=(1,2), p_2=(1,5), p_3=(3,4)\). Their \(x\)-values are \(0, 1, 1, 3\). Traversing from \(p_0\) to \(p_3\), the sequence \(0 \le 1 \le 1 \le 3\) is non-decreasing. Therefore the chain is \(x\)-monotone (non-strict). The equal \(x\)-values at \(p_1\) and \(p_2\) indicate that some segment portion may be vertical or that the chain pauses in \(x\); this does not break non-strict monotonicity.

7.2 Example: identifying non-monotone “turn-back” behavior

Let \(p_0=(0,0), p_1=(2,1), p_2=(1,3), p_3=(3,2)\). The \(x\)-values are \(0, 2, 1, 3\). Since \(2 \nleq 1\), the chain decreases in \(x\) when moving from \(p_1\) to \(p_2\). The chain is therefore not \(x\)-monotone (non-decreasing). Geometrically, the path “turns back” in the vertical-slice sense: there exists an intermediate \(x\)-slice that the chain crosses in both forward and backward order along the traversal.

7.3 Example: splitting into monotone subchains

Take \(x\)-projections \(0, 3, 1, 4, 2\) along a vertex sequence. A non-decreasing monotone segmentation might be:

  • subchain A: vertices with projections \(0, 3\),
  • subchain B: vertices with projections \(1, 4\),
  • subchain C: vertex with projection \(2\) alone (or paired with \(2\) depending on the chosen scheme).

Cuts occur at the indices where decreases occur (e.g., \(3 \to 1\) and \(4 \to 2\)). Each resulting subchain can then be processed by algorithms requiring monotonicity.

7.4 Common pitfalls and how to avoid them

  • Confusing strict vs non-strict: A chain with equal projected values is non-strictly monotone but may fail strict checks.
  • Checking only endpoints: Ensuring monotonicity requires verifying the entire vertex sequence (or equivalent edge behavior), not just extremes.
  • Floating-point comparisons: With real data, tiny numerical noise can be misinterpreted as genuine decreases. Use tolerances or exact representations when classification matters.
  • Ignoring direction convention: Monotonicity is directional. A chain might be non-decreasing in \(x\) but would be non-increasing in the reversed traversal. Confirm the intended traversal orientation.

8 References and Further Reading

Standard references in computational geometry and planar subdivision theory discuss monotone chains primarily in the context of monotone polygons, sweep-line methods, and polygon triangulation. Common topics include projection-based monotonicity, connectedness properties under directional slicing, and decomposition algorithms that rely on monotone structure.