CoreSource checked

Hausdorff Distance

Measures the largest nearest-neighbor gap between two point sets or shapes.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Intermediate
Family: Shape Similarity
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 7
Code example: Ready
Visualization: Ready

Overview

Hausdorff Distance compares two sets by finding, for each point in one set, the distance to the nearest point in the other set, then taking the worst such gap.

Core Concepts

shape distanceshape similaritygeometric primitivessequence alignmentgeometry

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use it when the worst unmatched point matters.
Use it to compare boundaries, point clouds, or sampled shapes.
Use directed Hausdorff distance when asymmetry is meaningful.

When Not to Use

Avoid it when average similarity matters more than the worst outlier.
Avoid it on noisy point sets without outlier handling.
Avoid comparing shapes before aligning coordinate systems.

What It Does

Measures worst-case set discrepancy
Uses nearest-neighbor distances between shapes or point sets

Use Cases

Shape comparison
Geometry validation
Trajectory or contour similarity checks

Inputs

Points, segments, polygons, or geometric primitives
Query or construction parameters

Outputs

Geometric decision, measurement, or constructed structure

Key Formulas (1)

Hausdorff distance

H(A,B) = max(max_a min_b d(a,b), max_b min_a d(a,b))

H(A,B) = max(max_a min_b d(a,b), max_b min_a d(a,b))

Measures the largest nearest-neighbor gap between two sets.

Pseudocode

1.Normalize input coordinates, primitives, or pixel buffers and initialize spatial data structures for shape distance.
2.Establish the sweep event queue, hierarchy, or scale-space pyramid required by Hausdorff Distance.
3.Process geometric predicates or pixel neighborhoods by finding, for each point in one set, the distance to the nearest point in the other set, then taking the worst such gap (H(A,B) = max(max_a min_b d(a,b), max_b min_a d(a,b))).
4.Resolve boundary degeneracies, occlusions, or threshold suppressions to maintain consistency.
5.Output the final shape similarity primitives, descriptors, or composited buffer.

Canonical Example

Input: A = {(0,0), (1,0)}, B = {(0,0), (2,0)}
Output: Hausdorff distance = 1
Explanation: The farthest nearest-neighbor gap is between the endpoints at 1 and 2.

Implementation Notes

Compute nearest-neighbor distance from every point in A to B and from B to A for the symmetric distance.
Use spatial indexes for large point sets.
Normalize or align shapes before comparing them.

Common Pitfalls

Letting one outlier dominate the distance.
Confusing directed and undirected Hausdorff distance.
Comparing sampled shapes with very different sampling density.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show measuring the largest nearest-neighbor gap between two point sets on a small shape distance example.

Step 1 of 5: Normalize input coordinates, primitives, or pixel buffers and initialize spatial data structures for shape distance.

geometry-mechanism

Notes

Hausdorff Distance operates in O(n log n) time and O(n) space within the Shape Similarity family. Key governing relation: H(A,B) = max(max_a min_b d(a,b), max_b min_a d(a,b)). Often compared with Voronoi-Based Medial Axis and Frechet Distance.