Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-09T02:40:46.889Z Has data issue: false hasContentIssue false
  • English
  • Français

An Improved Bound for k-Sets in Four Dimensions

Published online by Cambridge University Press:  20 May 2010

MICHA SHARIR
MICHA SHARIR*
Affiliation:
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA (e-mail: michas@post.tau.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that the number of halving sets of a set of n points in ℝ4 is O(n4−1/18), improving the previous bound of [10] with a simpler (albeit similar) proof.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 1 , January 2011 , pp. 119 - 129
Copyright
Copyright © Cambridge University Press 2010

References

[1]Agarwal, P., Aronov, B., Chan, T. and Sharir, M. (1998) On levels in arrangements of lines, segments, planes, and triangles. Discrete Comput. Geom. 19 315–331.CrossRefGoogle Scholar
[2]Ajtai, M., Chvátal, V., Newborn, M. M. and Szemerédi, E. (1982) Crossing-free subgraphs. Ann. Discrete Math. 12 9–12.Google Scholar
[3]Andrzejak, A. and Welzl, E. (2003) In between k-sets, j-facets, and i-faces: (i, j)-partitions. Discrete Comput. Geom. 29 105–131.CrossRefGoogle Scholar
[4]Blagojeviç, V. M., Matschke, B. and Ziegler, G. M. Optimal bounds for the colored Tverberg problem. arXiv:0910.4987Google Scholar
[5]Dey, T. (1998) Improved bounds for planar k-sets and related problems. Discrete Comput. Geom. 19 373–382.CrossRefGoogle Scholar
[6]Erdős, P., Lovász, L., Simmons, A. and Strauss, E. G. (1973) Dissection graphs of planar point sets. In Survey Combinat. Theory, Sympos. (Colorado State University 1971), pp. 139–149.CrossRefGoogle Scholar
[7]Leighton, F. T. (1983) Complexity Issues in VLSI, Foundations of Computing series, MIT Press.Google Scholar
[8]Lovász, L. (1971) On the number of halving lines. Ann. Univ. Sci. Budapest Rolando Eötvös Nom., Sec. Math. 14 107–108.Google Scholar
[9]Matoušek, J. (2002) Lectures on Discrete Geometry, Graduate Texts in Mathematics, Springer.CrossRefGoogle Scholar
[10]Matoušek, J., Sharir, M., Smorodinsky, S. and Wagner, U. (2006) On k-sets in four dimensions. Discrete Comput. Geom. 35 177–191.CrossRefGoogle Scholar
[11]Nivasch, G. (2008) An improved, simple construction of many halving edges. In Surveys on Discrete and Computational Geometry: Twenty Years Later (Goodman, J. E. et al. , eds), Vol. 453 of Contemporary Mathematics, AMS, pp. 299–305.CrossRefGoogle Scholar
[12]Sharir, M., Smorodinsky, S. and Tardos, G. (2001) An improved bound for k-sets in three dimensions. Discrete Comput. Geom. 26 195–204.CrossRefGoogle Scholar
[13]Tóth, G. (2001) Point sets with many k-sets. Discrete Comput. Geom. 26 187–194.CrossRefGoogle Scholar
[14]Živaljević, R. T. and Vrećica, S. T. (1992) The colored Tverberg theorem and complexes of injective functions. J. Combin. Theory Ser. A 61 309–318.CrossRefGoogle Scholar