Article

On overlays and minimization diagrams

Authors:

Vladlen Koltun,

Micha SharirAuthors Info & Claims

SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

Pages 395 - 401

https://doi.org/10.1145/1137856.1137914

Published: 05 June 2006 Publication History

Abstract

The overlay of 2≤m≤d minimization diagrams of n surfaces in R^d is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in R^d+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections of d-variate semi-algebraic surfaces, a tight bound on the compleity of the overlay of minimization diagrams of collections of hyperplanes, and faster algorithms for constructing such overlays. Further algoithmic implications are discussed.

References

[1]

P. K. Agarwal, B. Aronov, S. Har-Peled, and M. Sharir. Approximation and exact algorithms for minimum-width annuli and shells. Discrete Comput. Geom., 24(4):687--705, 2000.]]

Digital Library

[2]

P. K. Agarwal, B. Aronov, and M. Sharir. Computing envelopes in four dimensions with applications. SIAM J. Comput., 26:1714--1732, 1997.]]

Digital Library

[3]

P. K. Agarwal, B. Aronov, and M. Sharir. Exact and approximation algorithms for minimum-width cylindrical shells. Discrete Comput. Geom., 26:307--320, 2001.]]

Digital Library

[4]

P. K. Agarwal, O. Schwarzkopf, and M. Sharir. The overlay of lower envelopes and its applications. Discrete Comput. Geom., 15:1--13, 1996.]]

Digital Library

[5]

P. K. Agarwal and M. Sharir. Arrangements and their applications. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 49--119. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.]]

[6]

S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Springer Verlag, Berlin, 2003.]]

Digital Library

[7]

P. J. Besl and N. D. McKay. A method for registration of 3-d shapes. IEEE Trans. Pattern Anal. Mach. Intell., 14(2):239--256, 1992.]]

Digital Library

[8]

T. M. Chan. Approximating the diameter, width, smallest enclosing cylinder and minimum-width annulus. Internat. J. Comput. Geom. Appl., 12(2):67--85, 2002.]]

[9]

B. Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom., 10:377--409, 1993.]]

Digital Library

[10]

K. L. Clarkson. A randomized algorithm for closest-point queries. SIAM J. Comput., 17:830--847, 1988.]]

Digital Library

[11]

C. A. Duncan, M. T. Goodrich, and E. A. Ramos. Efficient approximation and optimization algorithms for computational metrology. In Proc. 8th ACM-SIAM Annu. Sympos. Discrete Algo., pages 121--130, 1997.]]

Digital Library

[12]

H. Ebara, N. Fukuyama, H. Nakano, and Y. Nakanishi. Roundness algorithms using the Voronoi diagrams. In Abstracts 1st Canad. Conf. Comput. Geom., page 41, 1989.]]

[13]

H. Edelsbrunner. The upper envelope of piecewise linear functions: Tight complexity bounds in higher dimensions. Discrete Comput. Geom., 4:337--343, 1989.]]

Digital Library

[14]

H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements. Discrete Comput. Geom., 1:25--44, 1986.]]

[15]

E. Ezra and M. Sharir. Bounds for the ICP algorithm. These proceedings, 2005.]]

Digital Library

[16]

L. J. Guibas, D. Halperin, J. Matoušek, and M. Sharir. On vertical decomposition of arrangements of hyperplanes in four dimensions. Discrete Comput. Geom., 14:113--122, 1995.]]

Digital Library

[17]

V. Koltun and M. Sharir. The partition technique for overlays of envelopes. SIAM J. Comput., 32:841--863, 2003.]]

[18]

V. Koltun and C. Wenk. Matching polyhedral terrains using overlays of envelopes. Algorithmica, 41:159--183, 2005.]]

Digital Library

[19]

P. McMullen. The maximal number of faces of a convex polytope. Mathematika, 17:179--184, 1970.]]

[20]

M. Sharir. Almost tight upper bounds for lower envelopes in higher dimensions. Discrete Comput. Geom., 12:327--345, 1994.]]

Digital Library

[21]

M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.]]

Digital Library

[22]

G. M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. Revised edition 1998.]]

Cited By

Ezra ESharir MEfrat A(2018)On the performance of the ICP algorithmComputational Geometry: Theory and Applications10.1016/j.comgeo.2007.10.00741:1-2(77-93)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.comgeo.2007.10.007
Ezra ESharir MEfrat AAmenta NCheong O(2006)On the ICP algorithmProceedings of the twenty-second annual symposium on Computational geometry10.1145/1137856.1137873(95-104)Online publication date: 5-Jun-2006
https://dl.acm.org/doi/10.1145/1137856.1137873

Index Terms

On overlays and minimization diagrams
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

On Overlays and Minimization Diagrams

The overlay of 2≤m≤d minimization diagrams of n surfaces in źd is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in źd+mź1. This elementary observation leads to a new bound on the complexity of the overlay of ...
The Overlay of Minimization Diagrams in a Randomized Incremental Construction

In a randomized incremental construction of the minimization diagram of a collection of n hyperplanes in ℝ^d, for d≥2, the hyperplanes are inserted one by one, in a random order, and the minimization diagram is updated after each insertion. We show that ...
The Overlay of Minimization Diagrams in a Randomized Incremental Construction

In a randomized incremental construction of the minimization diagram of a collection of n hyperplanes in źd, for dź2, the hyperplanes are inserted one by one, in a random order, and the minimization diagram is updated after each insertion. We show that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

June 2006

500 pages

ISBN:1595933409

DOI:10.1145/1137856

Program Chairs:
Nina Amenta
University of California at Davis
,
Otfried Cheong
Korea Advanced Institute of Science and Technology

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG06

Sponsor:

SoCG06: 22nd Annual Symposium on Computational Geometry

June 5 - 7, 2006

Arizona, Sedona, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
168
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ezra ESharir MEfrat A(2018)On the performance of the ICP algorithmComputational Geometry: Theory and Applications10.1016/j.comgeo.2007.10.00741:1-2(77-93)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.comgeo.2007.10.007
Ezra ESharir MEfrat AAmenta NCheong O(2006)On the ICP algorithmProceedings of the twenty-second annual symposium on Computational geometry10.1145/1137856.1137873(95-104)Online publication date: 5-Jun-2006
https://dl.acm.org/doi/10.1145/1137856.1137873

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents