Computational Geometry · 1997 · 130 citations · 24 references
ComputingComputer ScienceMathematicsAlgorithmsComputer VisionGeometryConvex GeometryGeometric ApproximationGeometric OptimizationGeometry ProcessingLine Segment IntersectionShape AnalysisComplexityCorrespondence ProblemGeometric MatchingGeometric Pattern AnalysisHausdorff DistanceMinimum DistanceShape MatchingUpper Bounds
Given two planar sets A and B, we examine the problem of determining the smallest ϵ such that there is a Euclidean motion (rotation and translation) of A that brings each member of A within distance ϵ of some member of B. We establish upper bounds on the combinatorial complexity of this subproblem in model-based computer vision, when the sets A and B contain points, line segments, or (filled-in) polygons. We also show how to use our methods to substantially improve on existing algorithms for finding the minimum Hausdorff distance under Euclidean motion.
24
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Computational geometry. an introduction
Franco P. Preparata, Michael Ian Shamos · 1985 · 2.4K citations
Algorithms in Combinatorial Geometry.
Jacob E. Goodman, Herbert Edelsbrunner · American Mathematical Monthly · 1989 · 1.8K citations
Richard Cole · SIAM Journal on Computing · 1988 · 734 citations