On k-hulls and related problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On k-hulls and related problems

Full text

Pdf (1.01 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the sixteenth annual ACM symposium on Theory of computing table of contents

Pages: 154 - 166

Year of Publication: 1984

ISBN:0-89791-133-4

Authors

Richard Cole
Micha Sharir
Chee K. Yap

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 24, Citation Count: 5

Additional Information:

abstract 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/800057.808677 What is a DOI?

ABSTRACT

For any set X of points (in any dimension) and any k &equil; 1,2, ..., we introduce the concept of the k-hull of X. This unifies the well-known notion of 'convex hulls' with the notion of 'centers' recently introduced by F.F. Yao. The concept is intimately related to some other concepts (k-belts, k-sets) studied by Edelsbrunner, Welzl, Lovász, Erdös and others. Several computational problems related to k-hulls are studied here. Some of our algorithms are of interest in themselves because of the techniques employed; in particular, the 'parametric' searching technique of Megiddo is used in a nontrivial way. We will also extend Megiddo's technique to Las Vegas algorithms. Our results have applications to a variety of problems in computational geometry: efficient computation of the 'cut' guaranteed by the classical 'Ham Sandwich theorem', faster preprocessing time for polygon retrieval, and theoretical improvements to a problem of intersecting lines and points posed by Hopcroft.

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	M. K. Agoston, Algebraic Topology, Marcel Dekker, New York, 1976.
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	4	B. Chazelle, "Optimal algorithms for computing depths and layers", Brown University Technical Report No. CS-83-13, March 1983.
	5	R. Cole and C. K. Yap, "A parallel median algorithm", preliminary version, September 1983.
	6	D. Dobkin and H. Edelsbrunner, private communication.
	7	L. Dubins and E. Spanier, "How to cut a cake fairly", AMM, 68(1961), 1-17.
	8	H. Edelsbrunner and E. Welzl, "On the number of line-separations of a finite set in the plane", to appear, J. Comb. Theory, A.
	9	H. Edelsbrunner and E. Welzl, "Halfplanar Range Estimation", Report F98, Inst. for Inf. Proc., Tech. Univ. of Graz, Austria (1982).
	10	H. Edelsbrunner and E. Welzl, "Halfplanar range search in linear space and O(n0.695) query time", Report F111, Inst. for Inf. Proc., Tech. Univ. of Graz, Austria (1983).
	11	P. Erdös, L. Lovász, A. Simmons and E. G. Straus, "Dissection Graphs of Planar Point Sets", in A Survey of Combinatorial Theory, J. N. Srivastava et al, eds., North-Holland, 1973, 139-149.
	12	T. P. Hill, "Determining a fair border", AMM 90:7(1983)438-442.
	13	L. Lovász, "On the number of halving lines", Ann. Univ. Sci. Budapest, Eötvos Sect. Mat. 14, 1971, 107-108.
	14	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	15	D. Muller and F. Preparata, Finding the intersection of two convex polyhedra, Theoretical Computer Science, 7(1979), 217-236.
	16	M. H. Overmars and J. van Leeuwen, "Maintenance of configurations in the plane", JCSS, 23(1981), 166-204.
	17	F. Preparata, New Parallel Sorting Schemes, IEEE Trans. Comput., C-27(1978),pp.669-673.
	18	L. Valiant, "Parallelism in Comparison Problems", SIAM J. Comp., Vol.4, No.3, 1975, 348-355.
	19	D. Willard, "Polygon Retrieval", SIAM J. Comp. 11, 1982, 149-165.
	20	I. M. Yaglom and V. G. Boltyanskii, Convex Figures, (trans.) Holt, Rinehart and Winston, 1961.
	21	F. Frances Yao, A 3-space partition and its applications, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.258-263, December 1983 [doi>10.1145/800061.808755]

CITED BY 5

	K L Clarkson, Further applications of random sampling to computational geometry, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.414-423, May 28-30, 1986, Berkeley, California, United States
	A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States
	K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	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
	Bernard Chazelle , Herbert Edelsbrunner, An improved algorithm for constructing kth-order Voronoi diagrams, Proceedings of the first annual symposium on Computational geometry, p.228-234, June 05-07, 1985, Baltimore, Maryland, United States