On-line construction of the convex hull of a simple polyline

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

On-line construction of the convex hull of a simple polyline

Source

Information Processing Letters archive
Volume 25 , Issue 1 (April 1987) table of contents

Pages: 11 - 12

Year of Publication: 1987

ISSN:0020-0190

Author

Avraham A. Melkman

Ben Gurion Univ. of the Negev, Beer Sheva, Israel

Publisher

Elsevier North-Holland, Inc. Amsterdam, The Netherlands, The Netherlands

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 32

Additional Information:

cited by index terms collaborative colleagues

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

DOI Bookmark:	10.1016/0020-0190(87)90086-X

CITED BY 32

	Paul J. Heffernan , Joseph S. B. Mitchell, Structured visibility profiles with applications to problems in simple polygons (extended abstract), Proceedings of the sixth annual symposium on Computational geometry, p.53-62, June 07-09, 1990, Berkley, California, United States
	David Dobkin , Leonidas Guibas , John Hershberger , Jack Snoeyink, An efficient algorithm for finding the CSG representation of a simple polygon, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.31-40, Aug. 1988
	John Hershberger , Jack Snoeyink, An O(nlogn) implementation of the Douglas-Peucker algorithm for line simplification, Proceedings of the tenth annual symposium on Computational geometry, p.383-384, June 06-08, 1994, Stony Brook, New York, United States
	Kasturi R. Varadarajan, Approximating monotone polygonal curves using the uniform metric, Proceedings of the twelfth annual symposium on Computational geometry, p.311-318, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Esther M. Arkin , Joseph S. B. Mitchell , Subhash Suri, Optimal link path queries in a simple polygon, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.269-279, September 1992, Orlando, Florida, United States
	J. Friedman , J. Hershberger , J. Snoeyink, Compliant motion in a simple polygon, Proceedings of the fifth annual symposium on Computational geometry, p.175-186, June 05-07, 1989, Saarbruchen, West Germany
	Edwin M. Knorr , Raymond T. Ng, Finding Aggregate Proximity Relationships and Commonalities in Spatial Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.884-897, December 1996
	P. L. Lin , W. H. Tan, An efficient method for the retrieval of objects by topological relations in spatial database systems, Information Processing and Management: an International Journal, v.39 n.4, p.543-559, July 2003
	O. El Badawy , M. S. Kamel, Hierarchical representation of 2-D shapes using convex polygons: a contour-based approach, Pattern Recognition Letters, v.26 n.7, p.865-877, 15 May 2005
	Godfried Toussaint, The Erdős-Nagy theorem and its ramifications, Computational Geometry: Theory and Applications, v.31 n.3, p.219-236, June 2005
	Arijit Laha , Amitava Sen , Bhabani P. Sinha, Parallel algorithms for identifying convex and non-convex basis polygons in an image, Parallel Computing, v.31 n.3+4, p.290-310, March/April 2005
	Christian Ronse, A Bibliography on Digital and Computational Convexity (1961-1988), IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.181-190, February 1989
	Isabelle Debled-Rennesson , Jean-Luc Rémy , Jocelyne Rouyer-Degli, Linear segmentation of discrete curves into blurred segments, Discrete Applied Mathematics, v.151 n.1-3, p.122-137, 1 October 2005
	Hervé Brönnimann , Timothy M. Chan, Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time, Computational Geometry: Theory and Applications, v.34 n.2, p.75-82, May 2006
	Timothy M. Chan, Three problems about simple polygons, Computational Geometry: Theory and Applications, v.35 n.3, p.209-217, October 2006
	Lilian Buzer, A simple algorithm for digital line recognition in the general case, Pattern Recognition, v.40 n.6, p.1675-1684, June, 2007
	Lilian Buzer, Optimal simplification of polygonal chain for rendering, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Lilian Buzer, Optimal simplification of polygonal chains for subpixel-accurate rendering, Computational Geometry: Theory and Applications, v.42 n.1, p.45-59, January, 2009
	Michela Bertolotto , Min Zhou, Efficient and consistent line simplification for web mapping, International Journal of Web Engineering and Technology, v.3 n.2, p.139-156, January 2007
	Fajie Li , Reinhard Klette, Analysis of the rubberband algorithm, Image and Vision Computing, v.25 n.10, p.1588-1598, October, 2007
	Martin Held , Joseph S. B. Mitchell, Triangulating input-constrained planar point sets, Information Processing Letters, v.109 n.1, p.54-56, December, 2008
	Alexandre Faure , Lilian Buzer , Fabien Feschet, Tangential cover for thick digital curves, Pattern Recognition, v.42 n.10, p.2279-2287, October, 2009
	S. Brlek , J. -O. Lachaud , X. Provençal , C. Reutenauer, Lyndon + Christoffel = digitally convex, Pattern Recognition, v.42 n.10, p.2239-2246, October, 2009
	Tristan Roussillon , Isabelle Sivignon , Laure Tougne, Measure of circularity for parts of digital boundaries and its fast computation, Pattern Recognition, v.43 n.1, p.37-46, January, 2010
	Eliseo Clementini , Roland Billen, Modeling and Computing Ternary Projective Relations between Regions, IEEE Transactions on Knowledge and Data Engineering, v.18 n.6, p.799-814, June 2006
	Timothy M. Chan, Three problems about simple polygons, Computational Geometry: Theory and Applications, v.35 n.3, p.209-217, October 2006
	Daniel Berend , Vladimir Braverman, A linear algorithm for computing convex hulls for random lines, ACM Transactions on Algorithms (TALG), v.5 n.4, p.1-21, October 2009
	Hervé Brönnimann , Timothy M. Chan, Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time, Computational Geometry: Theory and Applications, v.34 n.2, p.75-82, May 2006
	Godfried Toussaint, The Erdős--Nagy theorem and its ramifications, Computational Geometry: Theory and Applications, v.31 n.3, p.219-236, June 2005
	I. Debled-Rennesson , F. Feschet , J. Rouyer-Degli, Optimal blurred segments decomposition of noisy shapes in linear time, Computers and Graphics, v.30 n.1, p.30-36, February, 2006
	Tristan Roussillon , Hervé Piégay , Isabelle Sivignon , Laure Tougne , Franck Lavigne, Automatic computation of pebble roundness using digital imagery and discrete geometry, Computers & Geosciences, v.35 n.10, p.1992-2000, October, 2009
	Polychronis Manousopoulos , Vassileios Drakopoulos , Theoharis Theoharis, Parameter identification of 1D fractal interpolation functions using bounding volumes, Journal of Computational and Applied Mathematics, v.233 n.4, p.1063-1082, December, 2009