On Dynamic Voronoi Diagrams and the Minimum Hausdorff Distance for Point Sets Under Euclidean Motion in the Plane - Huttenlocher, Kedem, Kleinberg (ResearchIndex)

On Dynamic Voronoi Diagrams and the Minimum Hausdorff Distance for Point Sets Under Euclidean Motion in the Plane (1992) (Make Corrections) (18 citations)
Daniel P. Huttenlocher, Klara Kedem, Jon M. KleinbergSymposium on Computational Geometry

Home/Search Context Related

View or download:
cornell.edu/Info/People/kle...geom92.ps
cornell.edu/home/kleinber/geom92.ps
cornell.edu/Info/People/kle...geom92.ps
Cached:  PS.gz  PS  PDF  DjVu  Image  Update  Help

From:  cornell.edu/Info/People/kleinb... (more)
From:  cornell.edu/home/klein...kleinber
Homepages:  D.Huttenlocher  K.Kedem
  J.Kleinberg  [2]  HPSearch  (Update Links)

Rate this article:

(best)
Comment on this article

(Enter summary)
Abstract: We show that the dynamic Voronoi diagram of k sets of points in the plane, where each set consists of n points moving rigidly, has complexity O(n 2 k 2 s (k)) for some fixed s, where s (n) is the maximum length of a (n; s) Davenport-Schinzel sequence. This improves the result of Aonuma et. al., who show an upper bound of O(n 3 k 4 log k) for the complexity of such Voronoi diagrams. We then apply this result to the problem of finding the minimum Hausdorff distance between two point ... (Update)

Context of citations to this paper: More

...a DS (n; s) sequence whose depth is at most t, and let s;t (n) denote the maximum length of a DS (n; s; t) sequence. Huttenlocher et al. [77] proved that s;t (n) dn=te s (2t) see also Har Peled [72] This result has the following interesting consequence: Corollary 3.4 ( 77]...

.... for shapes given as equal cardinality sets of points [4, 6, 7, 10, 11, 15, 16, 20, 23, 24] and Hausdorff distance [2, 3, 4, 9, 12, 13, 14, 17, 18, 19, 22]. In this paper we consider the Hausdorff distance between (a) two sets of points under translation, b) two sets of...

Cited by: More
Computing the Maximum Overlap of Two Convex.. - de Berg.. (1996) (Correct)
Shape Matching: Similarity Measures and Algorithms - Veltkamp (2001) (Correct)
Geometric Matching under Noise: Combinatorial Bounds.. - Indyk, Motwani.. (Correct)

Active bibliography (related documents): More All
0.4: Geometric Pattern Matching under Euclidean Motion - Paul Chew (1993) (Correct)
0.3: Davenport-Schinzel Sequences and Their Geometric Applications - Agarwal, Sharir (1995) (Correct)
0.3: On Characteristic Points and Approximate Decision.. - Chew, Kedem, Schirra (Correct)

Similar documents based on text: More All
0.3: Computing a Double-Ray Center - For Planar Point (Correct)
0.2: 3D segment matching using the Hausdorff distance - Pascucci (Correct)
0.2: Matching Points into Pairwise-Disjoint Noise.. - Arkin, Kedem.. (1992) (Correct)

Related documents from co-citation: More All
11: The upper envelope of voronoi surfaces and its applications (context) - Huttenlocher, Kedem et al.
10: Geometric pattern matching under Euclidean motion - Chew, Goodrich et al. - 1993
8: Computational Geometry: An Introduction (context) - Preparata, Shamos - 1985

BibTeX entry: (Update)

Daniel P. Huttenlocher, Klara Kedem, and Jon M. Kleinberg. On dynamic voronoi diagrams and the minimum hausdorff distance for point sets under euclidean motion in the plane. In Proceedings of the Eighth Annual ACM Symposium on Computational Geometry, pages 110--119, 1992. http://citeseer.nj.nec.com/huttenlocher92dynamic.html More

@inproceedings{ huttenlocher92dynamic,
    author = "Daniel P. Huttenlocher and Klara Kedem and Jon M. Kleinberg",
    title = "On Dynamic Voronoi Diagrams and the Minimum Hausdorff Distance for Point Sets Under Euclidean Motion in the Plane",
    booktitle = "Symposium on Computational Geometry",
    pages = "110-119",
    year = "1992",
    url = "citeseer.nj.nec.com/huttenlocher92dynamic.html" }

Citations (may not include all citations):
223 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
71 Applications of parametric searching in geometric optimizati.. - Agarwal, Sharir et al. - 1992
65 Non-linearity of Davenport-Schinzel sequences and of general.. (context) - Hart, Sharir - 1986
53 An efficiently computable metric for comparing polygonal sha.. (context) - Arkin, Chew et al. - 1990
52 The upper envelope of Voronoi surfaces and its applications (context) - Huttenlocher, Kedem et al. - 1991
45 Sharp upper and lower bounds for the length of general Daven.. (context) - Agarwal, Sharir et al. - 1989
30 Voronoi diagrams of moving points in the plane (context) - Guibas, Mitchell et al. - 1991
22 Voronoi Diagrams of Moving Points in the Plane (context) - Fu - 1991
15 Congruence, similarity, and symmetries of geometric objects (context) - Alt, Mehlhorn et al. - 1988
12 Efficiently computing the Hausdorff distance for point sets .. (context) - Huttenlocher, Kedem - 1990
9 The problem of robust shape descriptors (context) - Mumford - 1987
8 Measuring the resemblance of polygonal shapes (context) - Alt, Behrends et al.
4 Maximin location of convex objects in a polygon and related .. (context) - Aonuma, Imai et al. - 1990

The graph only includes citing articles where the year of publication is known.

Documents on the same site (http://cs.cornell.edu/Info/People/kleinber/): More
Storage Management for Evolving Databases - Kleinberg, Motwani, Raghavan.. (1997) (Correct)
On Invariants of Sets of Points or Line Segments Under.. - Huttenlocher, Kleinberg (Correct)
Allocating Bandwidth for Bursty Connections - Kleinberg, Rabani, Tardos (1997) (Correct)

Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback