Article

Free access

Approximation and exact algorithms for minimum-width annuli and shells

Authors:

Pankaj K. Agarwal,

Boris Aronov,

Sariel Har-Peled,

Micha SharirAuthors Info & Claims

SCG '99: Proceedings of the fifteenth annual symposium on Computational geometry

Pages 380 - 389

https://doi.org/10.1145/304893.304992

Published: 13 June 1999 Publication History

PDF eReader

References

[1]

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

Digital Library

Google Scholar

[2]

P. K. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete Comput. Geom., 6 (t991), 407-422.

Digital Library

Google Scholar

[3]

P. K. Agarwal and J. Erickson, Geometric range searching and its relatives, in: Advances in Discrete and Computational Geometry (J. E. G. B. ChazeUe and R. Pollack, eds.), AMS Press, Providence, RI, 1998, pp. 1-56.

Google Scholar

[4]

P. K. Agarwal and J. Matou#ek. On range searching with semialgebraic sets. Discrete Comput. Geom., 11:393-418, 1994.

Digital Library

Google Scholar

[5]

P.K. Agarwal and M. Sharir, Efficient randomized algorithms for some geometric optimization problems, Discrete Cornput. Geom., 16 (1996), 317-337.

Digital Library

Google Scholar

[6]

P. K. Agarwal, M. Sharir, and S. Toledo, Applications of parametric searching in geometric optimization, J. Algorithms, 17 (1994), 292-318.

Digital Library

Google Scholar

[7]

A. Aggarwal, L. J. Guibas, J. Saxe, and P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete Comput. Geom., 4 (1989), 591-604.

Digital Library

Google Scholar

[8]

F. Aurenhammer. Voronoi diagrams: A survey of a fundamental geometric data structure. A CM Comput. Sure., 23:345-405, 1991.

Digital Library

Google Scholar

[9]

T. M. Chan, Geometric applications of a randomized optimization technique, Proc. l#th Annu. A CM Sympos. Comput. Geom., 1998, pp. 269-278.

Digital Library

Google Scholar

[10]

B. Chazelle, H. Edelsbrunner, L. J. Guibas, and M. Sharir, A singly-exponential stratification scheme for real semi-algebraic varieties and its applications, Theoret. Comput. Sci., 84 (1991), ??-105.

Digital Library

Google Scholar

[11]

M. de Berg, J. Bose, D. Bremner, S. Ramaswami, and G. Wilfong, Computing constrained minimum-width annuli of point sets, Proc. 5th Workshop Algorithms Data Struct., Lecture Notes Comput. Sei., Vol. 1272, Springer-Verlag, 1997, pp. 3-16.

Digital Library

Google Scholar

[12]

D. P. Dobkin and D. G. Kirkpatrick, A linear algorithm for determining the separation of convex polyhedra, J. Algorithms, 6 (1985), 381-392.

Crossref

Google Scholar

[13]

C. A. Duncan, M. T. Goodrich, and E. A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proc. 8th A CM-SIAM Sympos. Discrete Algorithms, 1997, pp. 121-130.

Digital Library

Google Scholar

[14]

M. Dyer and N. Megiddo, Linear programming in low dimensions, in: Handbook o.f Discrete and Computational Geometry (J. E. Goodman and J. O'Rourke, eds.), CRC Press LLC, Boca Raton, FL, 1997, pp. 699- 710.

Digital Library

Google Scholar

[15]

H. Ebara, N. Fukuyama, H. Nakano, and Y. Nakanishi, Roundness algorithms using the Voronoi diagrams, Abstracts 1st Canad. Con}. Comput. Geom., 1989, p. 41.

Google Scholar

[16]

H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision, SIAM J. Comput., 15 (1986), 317-340.

Digital Library

Google Scholar

[17]

O. Egecioglu and B. Kalantari, Approximating the diameter of a set of points in the Euclidean space, Inform. Process. Lett., 32 (1989), 205-211.

Digital Library

Google Scholar

[18]

L. W. Foster, GEO-METRICS II: The Application of Geometric Tolerancing Techniques, Addison-Wesley, Reading, MA, 1982.

Google Scholar

[19]

J. Garcla-Lopez and P. Ramos, Fitting a set of points by a circle, Proc. 13th Annu. A CM Sympos. Comput. Geom., 1997, pp. 139-146.

Digital Library

Google Scholar

[20]

S. Har-Peled, Constructing approximate shortest path maps in three dimensions, Proc. i$th Annu. A CM Sympos. Comput. Geom., 1998, pp. 383-391.

Digital Library

Google Scholar

[21]

D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2 (1987), 127- 151.

Digital Library

Google Scholar

[22]

R. Kumar, and D. Sivakumar, Roundness estimation via random sampling, Proc. l Oth A CM-SIAM Sympos. Discrete Algorithms, 1999, pp. 603-612.

Digital Library

Google Scholar

[23]

V. B. Le and D. T. Lee, Out-of-roundness problem revisited, IEEE Trans. Pattern Anal. Math. InteU., PAMI-13 (1991), 217-223.

Digital Library

Google Scholar

[24]

J. Matou#ek, M. Sharir, and E. Welzl, A subexponential bound for linear programming, Algorithmica, 16 (1996), 498-516.

Crossref

Google Scholar

[25]

K. Mehlhorn, T. Shermer, and C. Yap, A complete roundness classification procedure, Proc. 13th A nnu. A CM Sympos. Comput. Geom., 1997, pp. 129-138.

Digital Library

Google Scholar

[26]

J. S. B. Mitchell, D. M. Mount, and C. H. Papadimitriou, The discrete geodesic problem, SIAM J. Cornput., 16 (1987), 647-668.

Digital Library

Google Scholar

[27]

F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.

Digital Library

Google Scholar

[28]

T. J. Rivlin, Approximating by circles, Computing, 21 (1979), 93-104.

Crossref

Google Scholar

[29]

U. Roy, C. R. Liu, and T. C. Woo, Review of dimensioning and tolerancing: representation and processing, Comput. Aided Design, 23 (1991), 466-483.

Crossref

Google Scholar

[30]

U. Roy and X. Zhang, Establishment of a pair of concentric circles with the minimum radial separation for assessing roundness error, Comput. Aided Design, 24 (1992), 161-168.

Crossref

Google Scholar

[31]

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

Digital Library

Google Scholar

[32]

T. C. Shermer and C. K. Yap, Probing for near centers and relative roundness, Proc. A SME Workshop on Toleraneing and Metrology, 1995.

Google Scholar

[33]

M. Staid and R. Janardan, On the width and roundness of a set of points in the plane, Proe. 7th Canad. Conf. Comput. Geom., 1995, pp. 193-198.

Google Scholar

[34]

K. Swanson, D. T. Lee, and V. L. Wu, An optimal algorithm for roundness determination on convex polygons, Comput. Geom. Theory Appl., 5 (1995), 225-235.

Digital Library

Google Scholar

[35]

C. K. Yap and E.-C. Chang, Issues in the metrology of geometric tolerancing, Algorithms for Robotic Motion and Manipulation (J.-P. Laumond and M. Overmars, ed.), A.K. Peters, Wellesley, MA, 1997, pp. 393-400.

Google Scholar

Cited By

View all

Chan SPak I(2024)Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchyForum of Mathematics, Pi10.1017/fmp.2024.2012Online publication date: 11-Nov-2024
https://doi.org/10.1017/fmp.2024.20
Schöbel A(2020)Locating Dimensional Facilities in a Continuous SpaceLocation Science10.1007/978-3-030-32177-2_7(143-184)Online publication date: 17-Mar-2020
https://doi.org/10.1007/978-3-030-32177-2_7
Alkhalifa LBrimberg J(2016)Locating a minisum annulus: a new partial coverage distance modelTOP10.1007/s11750-016-0435-y25:2(373-393)Online publication date: 24-Oct-2016
https://doi.org/10.1007/s11750-016-0435-y
Show More Cited By

Index Terms

Approximation and exact algorithms for minimum-width annuli and shells

Recommendations

Minimum-width rectangular annulus

In this paper, we identify a minimum width rectangular annulus that encloses a given set of n points in a plane. We propose an O(n^2logn) time and O(n) space algorithm for this problem. To the best of our knowledge this is the first sub-cubic algorithm ...
Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells

Let S be a set of n points in \reals ³ . Let \opt be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S . We first present an O(n ⁵ ) -time algorithm ...
Approximation Algorithms for Minimum-Width Annuli and Shells

Let S be a set of n points in ^d. The "roundness" of S can be measured by computing the width * = *( S ) of the thinnest spherical shell (or annulus in ²) that contains S . This paper contains two main results related to computing an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '99: Proceedings of the fifteenth annual symposium on Computational geometry

June 1999

432 pages

ISBN:1581130686

DOI:10.1145/304893

Chairman:
Victor Milenkovic
Univ. of Miami, Coral Gables, FL

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SoCG99

Sponsor:

SoCG99: The Symposium on Computational Geometry

June 13 - 16, 1999

Florida, Miami Beach, USA

Acceptance Rates

SCG '99 Paper Acceptance Rate 44 of 103 submissions, 43%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
412
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)13

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chan SPak I(2024)Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchyForum of Mathematics, Pi10.1017/fmp.2024.2012Online publication date: 11-Nov-2024
https://doi.org/10.1017/fmp.2024.20
Schöbel A(2020)Locating Dimensional Facilities in a Continuous SpaceLocation Science10.1007/978-3-030-32177-2_7(143-184)Online publication date: 17-Mar-2020
https://doi.org/10.1007/978-3-030-32177-2_7
Alkhalifa LBrimberg J(2016)Locating a minisum annulus: a new partial coverage distance modelTOP10.1007/s11750-016-0435-y25:2(373-393)Online publication date: 24-Oct-2016
https://doi.org/10.1007/s11750-016-0435-y
Schöbel A(2015)Location of Dimensional Facilities in a Continuous SpaceLocation Science10.1007/978-3-319-13111-5_7(135-175)Online publication date: 21-Jan-2015
https://doi.org/10.1007/978-3-319-13111-5_7
CHAN T(2011)APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUSInternational Journal of Computational Geometry & Applications10.1142/S021819590200074812:01n02(67-85)Online publication date: 20-Nov-2011
https://doi.org/10.1142/S0218195902000748
Pal SBhowmick P(2011)Faster circularity estimation by randomizationIEEE Technology Students' Symposium10.1109/TECHSYM.2011.5783817(160-165)Online publication date: Jan-2011
https://doi.org/10.1109/TECHSYM.2011.5783817
Pal SBhowmick PBiswas A(2011)FACETProceedings of the 2011 Second International Conference on Emerging Applications of Information Technology10.1109/EAIT.2011.45(106-109)Online publication date: 19-Feb-2011
https://dl.acm.org/doi/10.1109/EAIT.2011.45
Roussillon TSivignon ITougne L(2010)Measure of circularity for parts of digital boundaries and its fast computationPattern Recognition10.1016/j.patcog.2009.06.01443:1(37-46)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1016/j.patcog.2009.06.014
Bandyopadhyay DSnoeyink JMunro I(2004)Almost-Delaunay simplicesProceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/982792.982851(410-419)Online publication date: 11-Jan-2004
https://dl.acm.org/doi/10.5555/982792.982851
Devillers OPreparata FShmoys D(2000)Evaluating the cylindricity of a nominally cylindrical point setProceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms10.5555/338219.338601(518-527)Online publication date: 1-Feb-2000
https://dl.acm.org/doi/10.5555/338219.338601
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Minimum-width rectangular annulus

Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells

Approximation Algorithms for Minimum-Width Annuli and Shells