Voronoi Region

Every Voronoi region is a convex polygon—a geometric shape where any line segment connecting two points within the region lies entirely inside it. This convexity property is guaranteed because the region is formed by the intersection of half-planes defined by the perpendicular bisectors between the region's constellation point and all neighboring points.

• Mathematical guarantee: Convexity holds for any finite set of generator points in Euclidean space
• Practical implication: Decision boundaries are always straight-line segments, never curved
• Edge case: Unbounded regions occur for points on the convex hull of the constellation, extending to infinity in directions with no closer neighbors

Each edge of a Voronoi region lies on the perpendicular bisector of the line segment connecting two adjacent constellation points. This geometric relationship ensures that every point on the boundary is exactly equidistant from both generator points, making it the optimal decision threshold where the receiver is equally likely to err in either direction.

• Construction rule: Draw the line between two points, then draw its perpendicular at the midpoint
• Noise immunity: The distance from the constellation point to the nearest boundary determines the margin against AWGN
• Non-uniform margins: Points near constellation edges have smaller noise margins than interior points

The Voronoi partition is the uniquely optimal decision region layout for minimizing symbol error probability under additive white Gaussian noise. This optimality stems from the fact that AWGN is spherically symmetric—the noise vector's probability density decreases monotonically with Euclidean distance from the transmitted point.

• Decision rule: Assign received sample r to constellation point s_i that minimizes ||r - s_i||²
• Maximum likelihood equivalence: Minimum-distance detection equals maximum likelihood detection for AWGN
• Suboptimal alternatives: Any non-Voronoi decision boundary increases error probability by including regions closer to incorrect constellation points

Voronoi regions have a dual geometric structure called the Delaunay triangulation. Connecting constellation points whose Voronoi regions share an edge produces a triangulation of the IQ plane where no point lies inside the circumcircle of any triangle. This duality is computationally exploited for efficient region construction.

• Direct correspondence: Each Voronoi vertex maps to a Delaunay triangle, and vice versa
• Empty circle property: The circumcircle of any Delaunay triangle contains no other constellation points
• Algorithmic benefit: Delaunay triangulation can be computed in O(n log n) time, from which Voronoi regions are derived in linear time

The topology of Voronoi regions—which points share boundaries and how many edges each region has—is invariant under uniform scaling, rotation, and translation of the entire constellation. Only the relative positions of constellation points matter, not their absolute coordinates or orientation.

• Rotation: Rotating the constellation rotates the Voronoi diagram identically
• Scaling: Uniformly scaling distances scales all region areas proportionally, preserving adjacency relationships
• Classification relevance: This invariance means modulation classifiers can operate on normalized, centered IQ samples without altering the fundamental decision geometry

The volume (area in 2D) of a Voronoi region directly relates to the probability of correct detection for that symbol under uniform noise conditions. Larger regions provide greater noise tolerance, but in practical constellations, region sizes vary—outer points typically have unbounded regions extending to infinity.

• Unbounded outer regions: Constellation points on the convex hull have infinite-area Voronoi regions, giving them lower error probability at high SNR
• Bounded inner regions: Interior points have finite, typically smaller regions, making them more susceptible to noise
• Shaping gain: Non-uniform constellations like APSK deliberately adjust region sizes to equalize error probabilities across symbols

A geometric threshold in the IQ plane that partitions the signal space into distinct Voronoi regions. Each boundary is the perpendicular bisector of the line segment connecting two adjacent constellation points. When a received symbol falls exactly on a boundary, the detector faces ambiguity—though in practice, noise makes this a zero-probability event. The shape and placement of these boundaries directly determine the symbol error rate for a given signal-to-noise ratio.

The optimal detection strategy for additive white Gaussian noise (AWGN) channels. The receiver calculates the Euclidean distance between the received noisy vector and every candidate constellation point, selecting the one with the smallest distance. This is mathematically equivalent to finding which Voronoi region contains the received sample. While optimal, brute-force computation becomes expensive for dense, high-order constellations like 4096-QAM, motivating efficient nearest-neighbor search algorithms.

The process of calculating the geometric center of a cluster of received IQ samples to estimate the original transmitted constellation point location. In blind modulation classification, centroid estimation is performed without prior knowledge of the modulation format:

• Simple averaging works for symmetric noise distributions
• K-Means clustering iteratively refines centroid positions
• Robust estimators like the median handle impulsive noise and outliers Accurate centroid recovery is a prerequisite for template matching against known constellation geometries.

A quantitative metric measuring the Euclidean distance between the ideal reference constellation point and the actual received signal point. EVM captures the combined impact of all impairments—noise, interference, nonlinear distortion, and phase noise—on modulation fidelity. In the context of Voronoi regions, EVM represents how far a received symbol has strayed from its intended centroid. When EVM becomes large enough to push a symbol across a decision boundary, a symbol error occurs.

A classification method that cross-correlates a reconstructed received constellation with a library of ideal reference templates. After compensating for scale and rotation, the modulation format whose template yields the highest similarity score is selected. The effectiveness of template matching depends on how well the recovered centroids align with the Voronoi region centers of each candidate modulation. This technique is particularly robust for distinguishing between PSK and QAM families at moderate SNR.

A bit-to-symbol mapping scheme where adjacent constellation points differ by only a single bit. Since the most likely symbol errors occur when noise pushes a received sample across a Voronoi boundary into a neighboring region, Gray coding ensures these dominant errors cause the minimum possible number of bit errors. For example, in 16-QAM with Gray mapping, crossing one decision boundary typically flips only 1 bit out of 4, rather than multiple bits simultaneously.