Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-25T18:37:52.155Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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