The upper envelope of Voronoi surfaces and its applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The upper envelope of Voronoi surfaces and its applications

Full text

Pdf (1.02 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the seventh annual symposium on Computational geometry table of contents

North Conway, New Hampshire, United States

Pages: 194 - 203

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Daniel P. Huttenlocher	Department of Computer Science, Cornell University, Ithaca, NY
Klara Kedem	Department of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel
Micha Sharir	Department of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 32, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/109648.109670 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ABB	Alt, H., Behrends, B. and Blomer, J., "Measuring the resemblance of polygonal shapes", manuscript (also to appear in Proc. Seventh ACM Symposium on Computational Geometry), 1991.
	ASS	P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
	Au	Aurenhammer, F., "Voronoi diagrams- A Survey", Tech. Rept. #B 90-09, Fachbereich Mathematik, Freie Universit{t Berlin, November 1990.
	CD	L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
	Ed	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	EGPPSS	Herbert Edelsbrunner , Leonidas J. Guibas , János Pach , Richard Pollack , Raimund Seidel , Micha Sharir, Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.214-229, July 11-15, 1988
	EGS	Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, The complexity and construction of many faces in arrangements of lines and of segments, Discrete & Computational Geometry, v.5 n.2, p.161-196, 1990 [doi>10.1007/BF02187784]
	EGS2	Edelsbrunner, H., Guibas, L.J., and Sharir, M., "The upper envelope of plecewlse linear functions", Discrete and Computational Geometry 4(1989), pp. 311-336.
	ES	Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
	GSS	L. J. Guibas, On the general motion-planning problem with two degrees of freedom, Discrete & Computational Geometry, v.4 n.5, p.491-521, 1989 [doi>10.1007/BF02187744]
	He	J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Information Processing Letters, v.33 n.4, p.169-174, December 1989 [doi>10.1016/0020-0190(89)90136-1]
	Ho	Berthold Klaus Paul Horn, Robot vision, MIT Press, Cambridge, MA, 1986
	HK	Daniel P. Huttenlocher , Klara Kedem, Computing the minimum Hausdorff distance for point sets under translation, Proceedings of the sixth annual symposium on Computational geometry, p.340-349, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98599]
	HKS	Huttenlocl~er, D.P., Kedem, K., and Sharir, M., "Tile upper envelope of Voronoi surfaces and its applications", Tech. Rept. ~200/91, Dept. of Computer Science, Tel-Arty University, February 1991.
	HS	S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
	LS	Leven, D., and Sharir, M. "Intersection and proximity problems and Voronoi diagrams", Advances in Robotics Vol. I: Algorithmic and Geometric Aspects of Robotics, J.T. Scwartz and C.K. Yap editors, Lawrence Erlbaum Associates, 1987, pp. 187-228.
	PaS	Pach, J., and Sharir, M., "The upper envelope of piecewise linear functions and the region enclosed by convex plates, I: combinatorial analysis", Discrete and Computational Geometry 4(1989) pp. 291-309.
	PS	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	SS	Schwartz, J.T., and Sharir, M., "On the piano movers problem' II. General techniques for computing topological properties of real algebraic manifolds'', Adv. Appl. Math. 4 (1983), 298-351.
	Ya	Yap, C.K, "An O(nlogn) algorithm for the Voronoi (tiagram of the set. of simple curve segments'', Discrete aT~d Computatio,al Geometry, 2(1987) pp. 365-393.

CITED BY 11

	Paul J. Heffernan , Stefan Schirra, Approximate decision algorithms for point set congruence, Proceedings of the eighth annual symposium on Computational geometry, p.93-101, June 10-12, 1992, Berlin, Germany
	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
	Nina Amenta, Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem, Proceedings of the tenth annual symposium on Computational geometry, p.340-347, June 06-08, 1994, Stony Brook, New York, United States
	Daniel P. Huttenlocher , Klara Kedem , Jon M. Kleinberg, On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane, Proceedings of the eighth annual symposium on Computational geometry, p.110-119, June 10-12, 1992, Berlin, Germany
	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991
	Boris Aronov , Micha Sharir, Castles in the air revisited, Proceedings of the eighth annual symposium on Computational geometry, p.146-156, June 10-12, 1992, Berlin, Germany
	Michael T. Goodrich , Joseph S. B. Mitchell , Mark W. Orletsky, Practical methods for approximate geometric pattern matching under rigid motions: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.103-112, June 06-08, 1994, Stony Brook, New York, United States
	D. P. Huttenlocher , G. A. Klanderman , W. A. Rucklidge, Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.850-863, September 1993
	William M. Wells, III, Statistical Approaches to Feature-Based Object Recognition, International Journal of Computer Vision, v.21 n.1-2, p.63-98, January. 1997
	Paul Viola , William M. Wells, III, Alignment by Maximization of Mutual Information, International Journal of Computer Vision, v.24 n.2, p.137-154, Sept. 1997
	Banghe Li , Yuefeng Shen , Bo Li, A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation, Information Processing Letters, v.106 n.2, p.52-58, April, 2008