An improved bound for k-sets in three dimensions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An improved bound for k-sets in three dimensions

Full text

Pdf (573 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: 43 - 49

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

Micha Sharir	School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY
Shakhar Smorodinsky	School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 69978, Israel
Gábor Tardos	Rényi Institute of the Hungarian Academy of Sciences, H-1364, Budapest, POB 127, Hungary

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): 3, Downloads (12 Months): 13, Citation Count: 1

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.336173 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	P. K. AGARWAL, B. ARONOV, T. M. CHAN, AND M. SHARIR, On levels in arrangements of lines, segments, planes, and triangles, Discrete Comput. Geom., 19 (1998), pp. 315-331.
	2	Artur Andrzejak , Boris Aronov , Sariel Har-Peled , Raimund Seidel , Emo Welzl, Results on k-sets and j-facets via continuous motion, Proceedings of the fourteenth annual symposium on Computational geometry, p.192-199, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276906]
	3	Boris Aronov , Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Rephael Wenger, Points and triangles in the plane and halving planes in space, Discrete & Computational Geometry, v.6 n.5, p.435-442, 1991 [doi>10.1007/BF02574700]
	4	I. BAR.~NY, Z. FUREDI, AND L. LOVASZ, On the number of halving planes, Combinatorica, 10 (1990), pp. 175-183.
	5	Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
	6	T. K. DEY, Improved bounds on planar ksets and related problems, Discrete Comput. Geom., 19 (1998), pp. 373-382.
	7	T. K. DEY AND H. EDELSBRUNNER, Counting triangle crossings and halving planes, Discrete Comput. Geom., 12 (1994), pp. 281-289.
	8	H. EDELSBRUNNER, P. VALTR, AND E. WELZL, Cutting dense point sets in half, Discrete Comput. Geom., 17 (1997), pp. 243-255.
	9	H. EDELSBRUNNER AND E. WELZL, On the number of line separations of a finite set in the plane, j. Combin. Theory Ser. A, 40 (1985), pp. 15-29.
	10	P. ERDOS, L. LovAsz, A. SIMMONS, AND E. STRAUS, Dissection graphs of planar point sets, in A Survey of Combinatorial Theory, J. N. Srivastava, ed., North-Holland, Amsterdam, Netherlands, 1973, pp. 139-154.
	11	L. LovAsz, On the number of halving lines, Annal. Univ. Scie. Budapest. de Rolando EStv6s Nominatae, Sectio Math., 14 (1971), pp. 107-108.
	12	J. PACH, Notes on geometric graph theory, Discrete and Computetional Geometry: Papers from the DIMACS Special Year, Dimacs Series in Discrete Mathematics and Theoretical Computer Science, 6 (1991), pp. 273-285.
	13	J. PACH AND P.K. AGARWAL, Combinatorial Geometry, Wiley-Interscience, New York, 1995.
	14	M. SHARIR, On k-sets in arrangements of curves and surfaces, Discrete Comput. Geom., 6 (1991), pp. 593-613.
	15	G. TSTH, On sets with many k-sets, manuscript, 1999.
	16	Emo Welzl, More on k-sets of finite sets in the plane, Discrete & Computational Geometry, v.1 n.1, p.95-100, 1986 [doi>10.1007/BF02187686]