On k-hulls and related problems

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 k-hulls and related problems

Source

SIAM Journal on Computing archive
Volume 16 , Issue 1 (February 1987) table of contents

Pages: 61 - 77

Year of Publication: 1987

ISSN:0097-5397

Authors

Richard Cole	New York Univ., New York, NY
Micha Sharir	Tel Aviv Univ., Tel Aviv, Israel
Chee K Yap	New York Univ., New York, NY

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

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

Additional Information:

cited by index terms review collaborative colleagues

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

DOI Bookmark:	10.1137/0216005

CITED BY 38

	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
	Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, Diameter, width, closest line pair, and parametric searching, Proceedings of the eighth annual symposium on Computational geometry, p.120-129, June 10-12, 1992, Berlin, Germany
	Micha Sharir , Shakhar Smorodinsky , Gábor Tardos, An improved bound for k-sets in three dimensions, Proceedings of the sixteenth annual symposium on Computational geometry, p.43-49, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	H. Edelsbrunner , L. J. Guibas , M. Sharir, The complexity of many faces in arrangements of lines of segments, Proceedings of the fourth annual symposium on Computational geometry, p.44-55, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Jeff Erickson, New lower bounds for Hopcroft's problem, Proceedings of the eleventh annual symposium on Computational geometry, p.127-137, June 05-07, 1995, Vancouver, British Columbia, Canada
	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
	Kim Miller , Suneeta Ramaswami , Peter Rousseeuw , Toni Sellarès , Diane Souvaine , Ileana Streinu , Anja Struyf, Fast implementation of depth contours using topological sweep, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.690-699, January 07-09, 2001, Washington, D.C., United States
	Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987
	P. Yamamoto , K. Kato , K. Imai , H. Imai, Algorithms for vertical and orthogonal L1 linear approximation of points, Proceedings of the fourth annual symposium on Computational geometry, p.352-361, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Jiří Matoušek , Chi-Yuan Lo , William Steiger, Ham-sandwich cuts in R^d, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.539-545, May 04-06, 1992, Victoria, British Columbia, Canada
	Pankaj K. Agarwal , Pavan K. Desikan, Approximation algorithms for layered manufacturing, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.528-537, January 09-11, 2000, San Francisco, California, United States
	Naoki Katoh , Takeshi Tokuyama, Notes on computing peaks in k-levels and parametric spanning trees, Proceedings of the seventeenth annual symposium on Computational geometry, p.241-248, June 2001, Medford, Massachusetts, United States
	Géza Tóth, Point sets with many k-sets, Proceedings of the sixteenth annual symposium on Computational geometry, p.37-42, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Shreesh Jadhav , Asish Mukhopadhyay, Computing a centerpoint of a finite planar set of points in linear time, Proceedings of the ninth annual symposium on Computational geometry, p.83-90, May 18-21, 1993, San Diego, California, United States
	Michael T. Goodrich, Geometric partitioning made easier, even in parallel, Proceedings of the ninth annual symposium on Computational geometry, p.73-82, May 18-21, 1993, San Diego, California, United States
	Hazel Everett , Jean-Marc Robert , Marc van Kreveld, An optimal algorithm for the (≤ k)-levels, with applications to separation and transversal problems, Proceedings of the ninth annual symposium on Computational geometry, p.38-46, May 18-21, 1993, San Diego, California, United States
	Herbert Edelsbrunner , Pavel Valtr , Emo Welzl, Cutting dense point sets in half, Proceedings of the tenth annual symposium on Computational geometry, p.203-209, June 06-08, 1994, Stony Brook, New York, United States
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	K. L. Clarkson , David Eppstein , Gary L. Miller , Carl Sturtivant , Shang-Hua Teng, Approximating center points with iterated radon points, Proceedings of the ninth annual symposium on Computational geometry, p.91-98, May 18-21, 1993, San Diego, California, United States
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Pankaj K. Agarwal , Mark de Berg , Jiří Matoušek , Otfried Schwarzkopf, Constructing levels in arrangements and higher order Voronoi diagrams, Proceedings of the tenth annual symposium on Computational geometry, p.67-75, June 06-08, 1994, Stony Brook, New York, United States
	Stefan Langerman , William Steiger, An optimal algorithm for hyperplane depth in the plane, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.54-59, January 09-11, 2000, San Francisco, California, United States
	Timothy M. Chan, An optimal randomized algorithm for maximum Tukey depth, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Naoki Katoh , Hisao Tamaki , Takeshi Tokuyama, Parametric polymatroid optimization and its geometric applications, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.517-526, January 17-19, 1999, Baltimore, Maryland, United States
	Ketan Mulmuley, Dehn-Sommerville relations, upper bound theorem, and levels in arrangements, Proceedings of the ninth annual symposium on Computational geometry, p.240-246, May 18-21, 1993, San Diego, California, United States
	Asish Mukhopadhyay , Alok Agrawal , Ravi Mohan Hosabettu, On the ordinary line problem in computational geometry, Nordic Journal of Computing, v.4 n.4, p.330-341, Winter 1997
	David Dobkin , Subhash Suri, Maintenance of geometric extrema ∈ , Journal of the ACM (JACM), v.38 n.2, p.275-298, April 1991
	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
	Micha Sharir, The interface between computational and combinatorial geometry, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Pankaj K. Agarwal , Sariel Har-Peled , Hai Yu, Robust shape fitting via peeling and grating coresets, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.182-191, January 22-26, 2006, Miami, Florida
	Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994
	Shankar Krishnan , Nabil H. Mustafa , Suresh Venkatasubramanian, Hardware-assisted computation of depth contours, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.558-567, January 06-08, 2002, San Francisco, California
	Manuel Abellanas , Mercè Claverol , Ferran Hurtado, Point set stratification and Delaunay depth, Computational Statistics & Data Analysis, v.51 n.5, p.2513-2530, February, 2007
	Harish Gopala , Pat Morin, Algorithms for bivariate zonoid depth, Computational Geometry: Theory and Applications, v.39 n.1, p.2-13, January, 2008
	Thorsten Bernholt , Robin Nunkesser , Karen Schettlinger, Computing the least quartile difference estimator in the plane, Computational Statistics & Data Analysis, v.52 n.2, p.763-772, October, 2007
	Gary L. Miller , Donald R. Sheehy, Approximate center points with proofs, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Timothy G. Abbott , Michael A. Burr , Timothy M. Chan , Erik D. Demaine , Martin L. Demaine , John Hugg , Daniel Kane , Stefan Langerman , Jelani Nelson , Eynat Rafalin , Kathryn Seyboth , Vincent Yeung, Dynamic ham-sandwich cuts in the plane, Computational Geometry: Theory and Applications, v.42 n.5, p.419-428, July, 2009
	Domagoj Matijević , Ralf Osbild, Finding the Θ-guarded region, Computational Geometry: Theory and Applications, v.43 n.2, p.207-218, February, 2010

INDEX TERMS

Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Geometrical problems and computations; Sorting and searching; Computations on discrete structures

G. Mathematics of Computing
G.3 PROBABILITY AND STATISTICS
Subjects: Statistical computing

General Terms:
Algorithms, Theory, Verification

REVIEW

"Vitit Kantabutra : Reviewer"

This paper presents several results pertaining to computing the k-hull of a finite set of points. The k-hull is a generalization of the convex hull. For any finite set X of points in any dimension and any positiv more...

Collaborative Colleagues:

Richard Cole: colleagues

Micha Sharir: colleagues

Chee K Yap: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player