Point sets with many k-sets

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Point sets with many k-sets

Full text

Pdf (458 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: 37 - 42

Year of Publication: 2000

ISBN:1-58113-224-7

Author

Géza Tóth

Massachusetts Institute of Technology and Hungarian Academy of Sciences

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): 16, Citation Count: 5

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.336171 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.

	AACS98	P. K. Agarwal, B. Aronov, T. M. Chan, M. Sharir: On levels in arrangements of lines, segments, planes, and triangles, Discrete and Computational Geometry 19 (1998), 315-331.
	AW99	A. Andrzejak, E. Welzl" k-sets and j-facets - A tour of discrete geometry, in preparation.
	ABFK92	N. Alon, I. B~r~ny, Z. Fiiredi, D. J. Kleitman: Point selections and weak e-nets for convex hulls, Combinatorics, Probability and Computing 1 (1992), 295-302.
	ACE91	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]
	AG86	N Alon , E Györi, The number of small semispaces of a finite set of points in the plane, Journal of Combinatorial Theory Series A, v.41 n.1, p.154-157, Jan. 1986 [doi>10.1016/0097-3165(86)90122-6]
	BFL90	I. B~r~ny, Z. Ffiredi, L. Lov~sz: On the number of halving planes, Combinatorica 10 (1990), 175- 183.
	CP86	B. Chazelle , F. P. Preparata, Halfspace range search: an algorithmic application of k-sets, Discrete & Computational Geometry, v.1 n.1, p.83-93, 1986 [doi>10.1007/BF02187685]
	CSY87	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]
	DE94	T. K. Dey, H. Edelsbrunner: Counting triangle crossings and halving planes, Discrete and Computational Geometry 12 (1994), 281-289.
	D98	T. K. Dey: Improved bounds for planar k-sets and related problems, Discrete and Computational Geometry 19 (1998), 373-382.
	E98	E. Early, personal communication.
	EW85	H. Edelsbrunner, E. Welzl: On the number of line separations of a finite set in the plane, Journal of Combinatorial Theory, Series A 38 (1985), 15-29.
	EW86	H. Edelsbrunner, E. Welzl: Constructing belts in two-dimensional arrangements with applications, SIAM Journal on Computing 15 (1986), 271-284.
	E87	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	EVW97	H. Edelsbrunner, P. Valtr, E. Welzl: Cutting dense point sets in half, Discrete and Computational Geometry 17 (1997),
	E92	D. Eppstein: Sets of points with many halving lines, Technical Report ICS, UCI, 92-86, (1992).
	E93	David Eppstein, Improved bounds for intersecting triangles and halving planes, Journal of Combinatorial Theory Series A, v.62 n.1, p.176-182, Jan. 1993 [doi>10.1016/0097-3165(93)90082-J]
	ELSS73	P. ErdSs, L. Lov~sz, A. Simmons, E. G. Straus: Dissection graphs of planar point sets, In: A Survey of Combinatorial Theory, (J. N. Srivastava et al. eds.), North Holland, Amsterdam, 1973, 139-149.
	GP84	J. E. Goodman, R. Pollack: On the number of k-subsets of a set of n points in the plane, Journal of Combinatorial Theory, Series A 36 (1984), 101-104.
	GP93	J. E. Goodman, R. Pollack: Allowable sequences and order types in discrete and computational geometry, In: New Trends in Discrete and Computational Geometry, (J. Pach, ed.), Algorithms and Combinatorics vol. 10, Springer-Verlag, New York, 1993, 103-134.
	KPP82	M. Klawe, M. Paterson, N. Pippenger: unpublished manuscript.
	LT1	L. Lov~sz: On the number of halving lines, Ann. Univ. Sci. Budapest Eb'tvSs Sect. Math. 14 (1971), 107-108.
	PA95	J. Pach, P. K. Agarwal: Combinatorial Geometry, John Wiley, New York, 1995.
	PSS92	János Pach , William Steiger , Endre Szemerédi, An upper bound on the number of planar K-sets, Discrete & Computational Geometry, v.7 n.2, p.109-123, 1992 [doi>10.1007/BF02187829]
	S91	M. Sharir: On k-sets in arrangements of curves and surfaces, Discrete and Computational Geometry 6 (1991), 593-613.
	SST99	M. Sharir, S. Smorodinsky, G. Tardos: An improved bound for k-sets in three dimensions, in preparation.
	W86	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]
	ZV92	Rade T. Živaljevic , Sinša T. Vrecica, The colored Tverberg's problem and complexes of injective functions, Journal of Combinatorial Theory Series A, v.61 n.2, p.309-318, Nov. 1992 [doi>10.1016/0097-3165(92)90028-S]

CITED BY 5

	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
	Radoš Radoičić , Géza Tóth, Monotone paths in line arrangements, Computational Geometry: Theory and Applications, v.24 n.3, p.129-134, April 2003
	Alina Beygelzimer , Stanislaw Radziszowski, On halving line arrangements, Discrete Mathematics, v.257 n.2-3, p.267-283, 28 November
	Joseph S. B. Mitchell , Joseph O'Rourke, Computational geometry, ACM SIGACT News, v.32 n.3, p.63-72, 09/01/2001
	Rom Pinchasi, Halving lines and measure concentration in the plane, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark