Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus

Full text

Pdf (918 KB)

Source

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

Clear Water Bay, Kowloon, Hong Kong

Pages: 300 - 309

Year of Publication: 2000

ISBN:1-58113-224-7

Author

Timothy M. Chan

Dept. of Computer Science, Univ. of Waterloo, Waterloo, Ontario N2L 3G1, Canada

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): 5, Downloads (12 Months): 46, 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/336154.336216 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 , Sariel Har-Peled , Micha Sharir, Approximation and exact algorithms for minimum-width annuli and shells, Proceedings of the fifteenth annual symposium on Computational geometry, p.380-389, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304992]
	2	P. K. Agarwal, B. Aronov, and M. Sharir. Line transversals of balls and smallest enclosing cylinders in three dimensions. Discrete Comput. Geom., 21:373- 388, 1999.
	3	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]
	4	Pankaj K. Agarwal , Jiří Matoušek , Subhash Suri, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, Computational Geometry: Theory and Applications, v.1 n.4, p.189-201, April 1992 [doi>10.1016/0925-7721(92)90001-9]
	5	P. K. Agarwal and M. Sharir. Efficient randomized algorithms for some geometric optimization problems. Discrete Comput. Geom., 16:317-337, 1996.
	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	Gill Barequet , Sariel Har-Peled, Efficiently approximating the minimum-volume bounding box of a point set in three dimensions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.82-91, January 17-19, 1999, Baltimore, Maryland, United States
	8	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
	9	Sergei N. Bespamyatnikh, An efficient algorithm for the three-dimensional diameter problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.137-146, January 25-27, 1998, San Francisco, California, United States
	10	Timothy M. Chan, Fixed-dimensional linear programming queries made easy, Proceedings of the twelfth annual symposium on Computational geometry, p.284-290, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237397]
	11	T. M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Cornput. Geom., 16:369-387, 1996.
	12	B. Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom., 10:377-409, 1993.
	13	B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Diameter, width, closest line pair and parametric searching. Discrete Comput. Geom., 10:183-196, 1993.
	14	Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Journal of Algorithms, v.21 n.3, p.579-597, Nov. 1996 [doi>10.1006/jagm.1996.0060]
	15	Kenneth L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, Journal of the ACM (JACM), v.42 n.2, p.488-499, March 1995 [doi>10.1145/201019.201036]
	16	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	17	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
	18	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
	19	M E Dyer, On a multidimensional search technique and its application to the Euclidean one centre problem, SIAM Journal on Computing, v.15 n.3, p.725-738, August 1986 [doi>10.1137/0215052]
	20	J. Garcia-L6pez, P. A. Ramos, and J. Snoeyink. Fitting a set of points by a circle. Discrete Comput. Geom., 20:389-402, 1998.
	21	Peter Gritzmann , Victor Klee, Computational convexity, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	22	Michael E. Houle , Godfried T. Toussaint, Computating the width of a set, Proceedings of the first annual symposium on Computational geometry, p.1-7, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323234]
	23	R. Janardan. On maintaining the width and diameter of a planar point-set online. Int. J. Comput. Geom. Appl., 3:331-344, 1993.
	24	Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
	25	Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
	26	J. Matou~ek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Comput. Geom., 10:215- 232, 1993.
	27	Jiří Matoušek , Otfried Schwarzkopf, A deterministic algorithm for the three-dimensional diameter problem, Computational Geometry: Theory and Applications, v.6 n.4, p.253-262, July 1996 [doi>10.1016/0925-7721(95)00025-9]
	28	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	29	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	30	Edgar A. Ramos, Construction of 1-d lower envelopes and applications, Proceedings of the thirteenth annual symposium on Computational geometry, p.57-66, June 04-06, 1997, Nice, France [doi>10.1145/262839.262864]
	31	E. Ramos. An optimal deterministic algorithm for computing the diameter of a 3-D point set. In these proceedings.
	32	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 [doi>10.1145/304893.304984]
	33	Elmar Schömer , Jürgen Sellen , Marek Teichmann , Chee-Keng Yap, Efficient Algorithms for the Smallest Enclosing Cylinder Problem, Proceedings of the 8th Canadian Conference on Computational Geometry, p.264-269, August 12-15, 1996
	34	Raimund Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete & Computational Geometry, v.6 n.5, p.423-434, 1991 [doi>10.1007/BF02574699]
	35	Micha Sharir , Emo Welzl, A Combinatorial Bound for Linear Programming and Related Problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.569-579, February 13-15, 1992

CITED BY 6

	Sariel Har-Peled, A practical approach for computing the diameter of a point set, Proceedings of the seventeenth annual symposium on Computational geometry, p.177-186, June 2001, Medford, Massachusetts, United States
	Pankaj K. Agarwal , Leonidas J. Guibas , Sariel Har-Peled , Alexander Rabinovitch , Micha Sharir, Penetration depth of two convex polytopes in 3D, Nordic Journal of Computing, v.7 n.3, p.227-240, Fall 2000
	Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Journal of Algorithms, v.46 n.2, p.115-139, February 2003
	Pankaj K. Agarwal , Cecilia M. Procopiuc , Kasturi R. Varadarajan, A (1 + ɛ)-approximation algorithm for 2-line-center, Computational Geometry: Theory and Applications, v.26 n.2, p.119-128, October 2003
	Joachim Gudmundsson , Herman Haverkort , Sang-Min Park , Chan-Su Shin , Alexander Wolff, Facility location and the geometric minimum-diameter spanning tree, Computational Geometry: Theory and Applications, v.27 n.1, p.87-106, January 2004
	Piyush Kumar , Joseph S. B. Mitchell , E. Alper Yildirim, Approximate minimum enclosing balls in high dimensions using core-sets, Journal of Experimental Algorithmics (JEA), 8, 2003