Output-sensitive results on convex hulls, extreme points, and related problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Output-sensitive results on convex hulls, extreme points, and related problems

Full text

Pdf (1.07 MB)

Source

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

Vancouver, British Columbia, Canada

Pages: 10 - 19

Year of Publication: 1995

ISBN:0-89791-724-3

Author

Timothy M. Chan

Department of Computer Science, University of British Columbia

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): 7, Downloads (12 Months): 34, Citation Count: 11

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/220279.220281 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 , Jiří Matoušek, Ray shooting and parametric search, SIAM Journal on Computing, v.22 n.4, p.794-806, Aug. 1993 [doi>10.1137/0222051]
	2	J. L. Bentley , H. T. Kung , M. Schkolnick , C. D. Thompson, On the Average Number of Maxima in a Set of Vectors and Applications, Journal of the ACM (JACM), v.25 n.4, p.536-543, Oct. 1978 [doi>10.1145/322092.322095]
	3	J. L. Bentley and J. Saxe. Decomposable searching problems I: static-to-dynamic transformations. J. Algorithms, 1:301-358, 1980.
	4	Timothy M. Y. Chan , Jack Snoeyink , Chee-Keng Yap, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.282-291, January 22-24, 1995, San Francisco, California, United States
	5	B. Chazelle. An optimal algorithm for computing convex layers. IEEE Trans. Information Theory, IT- 31:509-517, 1985.
	6	Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
	7	Donald R. Chand , Sham S. Kapur, An Algorithm for Convex Polytopes, Journal of the ACM (JACM), v.17 n.1, p.78-86, Jan. 1970 [doi>10.1145/321556.321564]
	8	B. Chazelle and J. Matou~ek. Derandomizing an output-sensitive convex hull algorithm in three dimensions. Manuscript, 1993.
	9	K. L. Clarkson. More output-sensitive geometric algorithms, in Proc. 35th IEEE Sympos. Found. of Comput. $ci., 695-702, 1994.
	10	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]
	11	D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection. Theoretical Comput. Sc~., 27:241-253, 1983.
	12	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	13	Herbert Edelsbrunner , Weiping Shi, An O(n log2h) time algorithm for the three-dimensional convex hull problem, SIAM Journal on Computing, v.20 n.2, p.259-269, April 1990 [doi>10.1137/0220016]
	14	Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
	15	H. Edelsbrunner and E. Welzl. Constructing belts in two-dimensional arrangements with applications. SIAM J. Comput., 15:271-284, 1986.
	16	Ioannis Emiris , John Canny, An efficient approach to removing geometric degeneracies, Proceedings of the eighth annual symposium on Computational geometry, p.74-82, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142694]
	17	R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett., 1:132-133, 1972.
	18	R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Inform. Process. Left., 2:18-21, 1973.
	19	David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
	20	Jiří Matoušek , Otfried Schwarzkopf, Linear optimization queries, Proceedings of the eighth annual symposium on Computational geometry, p.16-25, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142683]
	21	Jiří Matoušek, On geometric optimization with few violated constraints, Proceedings of the tenth annual symposium on Computational geometry, p.312-321, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178039]
	22	J. Matou~ek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Comput. Geom., 10:215- 232, 1993.
	23	P. McMullen. The maximal number of faces of a convex polytope. Mathematica, 17:179-184, 1970.
	24	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]
	25	K. Mulmuley, Output sensitive construction of levels and Voronoi diagrams in Rd of order 1 to k, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.322-330, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100259]
	26	K. Mulmuley. Computational Geometry: An introduction Through Randomized Algorithms. Prentice Hall, New York, 1993.
	27	Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994
	28	M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci., 23:166-204, 1981.
	29	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
	30	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	31	H. Raynaud. Sur l'enveloppe convexe des nuages des points al~atoires dans R'~. J. Appl. Probab., 7:35-48, 1970.
	32	M. Reichling, On the detection of a common intersection of k convex objects in the plane, Information Processing Letters, v.29 n.1, p.25-29, Sept. 15, 1988 [doi>10.1016/0020-0190(88)90127-5]
	33	Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
	34	R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
	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
	36	G. F. Swart. Finding the convex hull facet by facet. J. Algorithms, 6:17-48, 1985.

CITED BY 11

	Nina Amenta , Günter M. Ziegler, Shadows and slices of polytopes, Proceedings of the twelfth annual symposium on Computational geometry, p.10-19, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Neelima Gupta , Sandeep Sen, Faster output-sensitive parallel convex hulls for d≤3: optimal sublogarithmic algorithms for small outputs, Proceedings of the twelfth annual symposium on Computational geometry, p.176-185, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Nancy M. Amato , Edgar A. Ramos, On computing Voronoi diagrams by divide-prune-and-conquer, Proceedings of the twelfth annual symposium on Computational geometry, p.166-175, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	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
	Jeff Erickson, New lower bounds for convex hull problems in odd dimensions, Proceedings of the twelfth annual symposium on Computational geometry, p.1-9, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Sandeep Sen , Neelima Gupta, Distribution-sensitive algorithms, Nordic Journal of Computing, v.6 n.2, p.194-211, Summer 1999
	Neelima Gupta , Sandeep Sen, Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima, Journal of Parallel and Distributed Computing, v.63 n.4, p.488-500, April 2003
	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
	Ladislav Kavan , Ivana Kolingerova , Jiri Zara, Fast approximation of convex hull, Proceedings of the 2nd IASTED international conference on Advances in computer science and technology, p.101-104, January 23-25, 2006, Puerto Vallarta, Mexico
	L. Paul Chew, Exact computation of protein structure similarity, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Nina Amenta , Dominique Attali , Olivier Devillers, Complexity of Delaunay triangulation for points on lower-dimensional polyhedra, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1106-1113, January 07-09, 2007, New Orleans, Louisiana