advanced32 min studyLesson 925 in Mathematics

Voronoi diagrams and nearest neighbors

Build nearest-site regions from distance inequalities and retain the ties.

Before you begin

On this page

The question for today

What you’ll understand

Derive an ordinary Euclidean Voronoi cell as a half-plane intersection.
Use planar diagram complexity and point location for nearest-site queries.
Distinguish generic triple vertices from cocircular multiway ties.

A nearest-neighbor query can be converted into point location by partitioning the plane according to the closest site. We consider a finite set of distinct, unweighted point sites in the Euclidean plane. The closed cell of a site contains locations at least as close to it as to every other site. Closed cells overlap on ties, so they are not disjoint as sets; their interiors are disjoint and their shared boundaries form a subdivision. A query policy may return one nearest identifier or all ties, with different output costs.

Squared distances turn a curved-looking problem linear

Comparing squared distances cancels the query's squared norm, leaving one affine inequality. Thus the cell of a site is an intersection of closed half-planes and is convex, possibly unbounded. Its boundaries lie on perpendicular bisectors. An entire bisector need not be a diagram edge: a third site may be nearer on part of it. Distinguishing a pairwise equal-distance locus from the globally nearest-site boundary is essential when constructing a diagram from local calculations.

For distinct noncollinear sites in general position, finite Voronoi vertices have three incident cells, and the planar diagram has linear total complexity. The standard generic condition excludes four cocircular sites, while excluding three collinear sites simplifies related triangulation arguments. Collinear sites themselves still have a valid linear-size diagram, consisting of parallel-strip cells and no finite triple vertices. Coincident sites require merging their geometric locations while retaining whatever identifier multiplicity the query interface promises.

\|x-p\|^2\leq\|x-q\|^2\quad\Longleftrightarrow\quad 2(q-p)\cdot x\leq\|q\|^2-\|p\|^2.

A nearest-site comparison is a closed half-plane test; equality is a legitimate distance tie.↔ Scroll wide equations horizontally.

Preprocess once and query the resulting subdivision

Standard planar algorithms construct the ordinary point-site Voronoi diagram at sorting-scale time and linear space. Combining the diagram with an appropriate point-location structure gives logarithmic nearest-site queries, plus any explicitly requested tie output. These bounds assume fixed dimension two and constant-cost exact geometric operations in the abstract model. They do not transfer unchanged to arbitrary metrics, weighted sites, or high-dimensional diagrams, whose cell shapes and complexity can be very different.

At an interior query, the containing cell immediately identifies the unique nearest site. An edge query has at least two nearest sites, and a vertex query can have three or more. If all nearest identifiers are required, the output term must be included. If one is sufficient, a declared total order on site identifiers gives a deterministic tie rule. A coordinate tolerance that inconsistently changes which side of a boundary is selected can contradict other exact decisions and should not define this combinatorial policy.

T_{\mathrm{build}}(n)=O(n\log n),\qquad \text{diagram size}=O(n),\qquad T_{\mathrm{one\ nearest}}=O(\log n).

These are ordinary planar Euclidean point-site bounds with a suitable locator and a declared tie rule.↔ Scroll wide equations horizontally.

Cocircularity changes combinatorics without breaking distance

Four sites on an empty circle produce a Voronoi vertex where four cells can meet. The distances are perfectly well defined, even though a generic degree-three picture no longer applies. A triangulation-based construction must resolve that higher-order event consistently; it cannot infer a unique diagonal from an exactly zero incircle test. The next lesson distinguishes the natural Delaunay subdivision from a chosen triangular refinement. Both structures require attention to what a tie means geometrically.

Voronoi regions also make a useful verification target. Check that a proposed edge lies on the appropriate bisector and that its points are no farther from its two sites than from every other site. Check that every finite proposed vertex has the claimed equal distances and an empty nearest-site circle. These are necessary geometric certificates, although assembling them into a complete, correctly embedded subdivision also requires incidence and coverage checks. A handful of equal-distance equations alone does not establish the full diagram.

Work it through

Three sites with a right-triangle circumcenter

For $A=(0,0)$ , $B=(6,0)$ , $C=(0,8)$ , find A’s closed cell and the finite Voronoi vertex. Determine the nearest sites to $q=(4,1)$ and $r=(3,1)$ .

Comparing A with B gives $x\leq3$ ; comparing A with C gives $y\leq4$ . Thus A’s closed cell is the intersection of those two half-planes, including its shared boundary rays.
Their boundary lines meet at $(3,4)$ , whose squared distance to every site is $25$ . This is the unique finite Voronoi vertex; the A–B edge is only the ray $x=3$ , $y\leq4$ .
At q the squared distances to A,B,C are $17,5,65$ , so B is uniquely nearest. At r they are $10,10,58$ , so A and B tie, with C strictly farther away.

The result

Pairwise equal distance identifies a potential boundary, while comparison with every other site determines the actual Voronoi edge and nearest-site answer.

The living notebook

Explore the model

Interactive lab

Interactive lab · vectors

Cross a two-site perpendicular bisector

Fix sites $A=(0,0)$ , $B=(4,0)$ . Pause/Reset and set BOTH controls to angle $0$ degrees, magnitude $2$ : the endpoint $(2,0)$ has squared distance $4$ to each site. For a fresh comparison Pause/Reset and set BOTH to angle $60$ degrees, magnitude $2$ : endpoint $(1,\sqrt3)$ has squared distances $4$ and $12$ , so A wins. Changes retain the paused clock.

Vectorx / y projectionsTrace marker

x component: 1.393
y component: 0.975
Magnitude: 1.7

Angle35°Magnitude1.7

t = 0 s

Playback traces a fixed vector and its projections. Angle and magnitude set the geometry; the moving marker does not change them. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forThe vector endpoint supplies two query locations for a manually computed bisector. The instrument does not build a Voronoi diagram.

Pause & reason

Check your understanding

Interactive checks need JavaScript. You can still read the explanation.

Read the checkpoint explanation

Cocircularity creates a valid higher-order Voronoi vertex. Generic degree-three statements exclude this case, while a deterministic identifier rule can choose one of the true ties without changing the distances.

Your turn

Try it yourself

Place sites at $(1,1),(-1,1),(-1,-1),(1,-1)$ . Find the nearest-site set at the origin and at $(0,1/2)$ . Explain why demanding all ties affects a query-time specification.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Calculate squared distances to the upper and lower pairs separately.

Compare with the solution

At the origin every squared distance is $2$ , so all four sites are nearest. At $(0,1/2)$ the upper pair has squared distance $1+1/4=5/4$ , while the lower pair has $1+9/4=13/4$ ; exactly the two upper sites tie. Returning all nearest identifiers costs at least their number in output operations. In larger cocircular examples that number need not be a fixed constant, whereas returning one identifier under a fixed tie order can remain a single-answer query.

Keep the idea

Take it with you

Voronoi cells are intersections of distance-comparison half-planes.
The planar unweighted Euclidean assumptions are part of the linear-size theorem.
Distance ties remain valid geometry and require an explicit output policy.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.