Approximation and exact algorithms for minimum-width annuli and shells

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximation and exact algorithms for minimum-width annuli and shells

Full text

Pdf (1.08 MB)

Source

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

Miami Beach, Florida, United States

Pages: 380 - 389

Year of Publication: 1999

ISBN:1-58113-068-6

Authors

Pankaj K. Agarwal	Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NC
Boris Aronov	Department of Computer and Information Science, Polytechnic University, Brooklyn, NY
Sariel Har-Peled	School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel
Micha Sharir	School of Mathematical Sciences, 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): 3, Downloads (12 Months): 13, Citation Count: 6

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/304893.304992 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.

	1	Pankaj K. Agarwal , Boris Aronov , Micha Sharir, Computing Envelopes in Four Dimensions with Applications, SIAM Journal on Computing, v.26 n.6, p.1714-1732, Dec. 1997 [doi>10.1137/S0097539794265724]
	2	Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, v.6 n.5, p.407-422, 1991 [doi>10.1007/BF02574698]
	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.
	4	P. K. Agarwal and J. Matou#ek. On range searching with semialgebraic sets. Discrete Comput. Geom., 11:393-418, 1994.
	5	P.K. Agarwal and M. Sharir, Efficient randomized algorithms for some geometric optimization problems, Discrete Cornput. Geom., 16 (1996), 317-337.
	6	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Journal of Algorithms, v.17 n.3, p.292-318, Nov. 1994
	7	A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
	8	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 [doi>10.1145/116873.116880]
	9	Timothy M. Chan, Geometric applications of a randomized optimization technique, Proceedings of the fourteenth annual symposium on Computational geometry, p.269-278, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276915]
	10	Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, v.84 n.1, p.77-105, July 22, 1991 [doi>10.1016/0304-3975(91)90261-Y]
	11	Mark de Berg , Prosenjit Bose , David Bremner , Suneeta Ramaswami , Gordon T. Wilfong, Computing Constrained Minimum-Width Annuli of Point Sets, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.392-401, August 06-08, 1997
	12	D. P. Dobkin and D. G. Kirkpatrick, A linear algorithm for determining the separation of convex polyhedra, J. Algorithms, 6 (1985), 381-392.
	13	Christian A. Duncan , Michael T. Goodrich , Edgar A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.121-130, January 05-07, 1997, New Orleans, Louisiana, United States
	14	Martin Dyer , Nimrod Megiddo, Linear programming in low dimensions, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	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.
	16	Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
	17	Ömer E>ilde;ecio>ilde;lu , Bahman Kalantari, Approximating the diameter of a set of points in the Euclidean space, Information Processing Letters, v.32 n.4, p.205-211, Sept 1, 1989 [doi>10.1016/0020-0190(89)90045-8]
	18	L. W. Foster, GEO-METRICS II: The Application of Geometric Tolerancing Techniques, Addison-Wesley, Reading, MA, 1982.
	19	Jesús García-López , Pedro A. Ramos, Fitting a set of points by a circle, Proceedings of the thirteenth annual symposium on Computational geometry, p.139-146, June 04-06, 1997, Nice, France [doi>10.1145/262839.262919]
	20	Sariel Har-Peled, Constructing approximate shortest path maps in three dimensions, Proceedings of the fourteenth annual symposium on Computational geometry, p.383-391, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276927]
	21	D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2 (1987), 127- 151.
	22	Ravi Kumar , D. Sivakumar, Roundness estimation via random sampling, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.603-612, January 17-19, 1999, Baltimore, Maryland, United States
	23	Van-Ban Le , D. T. Lee, Out-of-Roundness Problem Revisited, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.3, p.217-223, March 1991 [doi>10.1109/34.75510]
	24	J. Matou#ek, M. Sharir, and E. Welzl, A subexponential bound for linear programming, Algorithmica, 16 (1996), 498-516.
	25	Kurt Mehlhorn , Thomas C. Shermer , Chee K. Yap, A complete roundness classification procedure, Proceedings of the thirteenth annual symposium on Computational geometry, p.129-138, June 04-06, 1997, Nice, France [doi>10.1145/262839.262917]
	26	Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
	27	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	28	T. J. Rivlin, Approximating by circles, Computing, 21 (1979), 93-104.
	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.
	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.
	31	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
	32	T. C. Shermer and C. K. Yap, Probing for near centers and relative roundness, Proc. A SME Workshop on Toleraneing and Metrology, 1995.
	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.
	34	Kurt Swanson , D. T. Lee , Vanban L. Wu, An optimal algorithm for roundness determination on convex polygons, Computational Geometry: Theory and Applications, v.5 n.4, p.225-235, Nov. 1995 [doi>10.1016/0925-7721(95)00004-6]
	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.

CITED BY 6

	Timothy M. Chan, Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus, Proceedings of the sixteenth annual symposium on Computational geometry, p.300-309, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Bernd Gärtner , Sven Schönherr, An efficient, exact, and generic quadratic programming solver for geometric optimization, Proceedings of the sixteenth annual symposium on Computational geometry, p.110-118, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Pankaj K. Agarwal , Boris Aronov , Micha Sharir, Exact and approximation algorithms for minimum-width cylindrical shells, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.510-517, January 09-11, 2000, San Francisco, California, United States
	Pedro A. Ramos, Computing roundness is easy if the set is almost round, Proceedings of the fifteenth annual symposium on Computational geometry, p.307-315, June 13-16, 1999, Miami Beach, Florida, United States
	Deepak Bandyopadhyay , Jack Snoeyink, Almost-Delaunay simplices: nearest neighbor relations for imprecise points, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Olivier Devillers , Franco P. Preparata, Evaluating the cylindricity of a nominally cylindrical point set, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.518-527, January 09-11, 2000, San Francisco, California, United States