skip to main content
10.1145/1064092.1064098acmconferencesArticle/Chapter ViewAbstractPublication PagessocgConference Proceedingsconference-collections
Article

Incidences of not-too-degenerate hyperplanes

Published: 06 June 2005 Publication History

Abstract

We present a multi-dimensional generalization of the Szemerédi-Trotter Theorem, and give a sharp bound on the number of incidences of points and not-too-degenerate hyperplanes in three- or higher-dimensional Euclidean spaces. We call a hyperplane not-too-degenerate if at most a constant portion of its incident points lie in a lower dimensional affine subspace.

References

[1]
Pankaj K. Agarwal and Boris Aronov, Counting facets and incidences, Discrete Comput. Geom. 7 (1992) 359--369.
[2]
Boris Aronov and Micha Sharir, Cell complexities in hyperplane arrangements, Discrete Comput. Geom. 32 (2004), 107--115.
[3]
József Beck, On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős, Combinatorica 3 (3-4) (1983), 281--297.
[4]
Peter Braβ and Christian Knauer, On counting point-hyperplane incidences, Comput. Geom. Theory Appl. 25 (1-2) (2003), 13--20.
[5]
Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, and Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990), 99--160.
[6]
Herbert Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.
[7]
Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, The complexity of many cells in arrangements of planes and related problems, Discrete Comput. Geom. 5 (1990), 197--216.
[8]
Herbert Edelsbrunner and David Haussler, The complexity of cells in three-dimensional arrangements, Discrete Math. 60 (1986), 139--146.
[9]
Herbert Edelsbrunner and Micha Sharir, A hyperplane incidence problem with applications to counting distances, in Proc. SIGAL International Symposium on Algorithms (T. Asano et al., eds.), vol. 450 of LNCS, Springer-Verlag, Berlin, 1990, pp. 419--428.
[10]
György Elekes, Sums versus products in Number Theory, Algebra and Erdős Geometry, vol 11 of Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 2002, pp. 241--290.
[11]
Jeff Erickson, New lower bounds for Hopcroft's problem, Discrete Comput. Geom. 16 (1996), 389--418.
[12]
Sten Hansen, A generalization of a theorem of Sylvester on the lines determined by a finite point set, Math. Scand. 16 (1965) 175--180.
[13]
Theodore S. Motzkin, The lines and planes connecting the points of a finite set, Trans. Amer. Math. Soc. 70 (1951), 451--464.
[14]
János Pach and Micha Sharir, Geometric incidences, in Towards a Theory of Geometric Graphs (J. Pach, ed.), vol. 342 of Contemporary Mathematics, Amer. Math. Soc., Providence, RI, 2004, pp. 185--223.
[15]
Endre Szemerédi and William T. Trotter Jr., Extremal problems in Discrete Geometry, Combinatorica 3 (3--4) (1983), 381--392.
[16]
László A. Székely, Crossing numbers and hard Erdő problems in discrete geometry, Combinatorics, Probability & Computing 6 (3) (1997), 353--358.
[17]
Csaba D. Tóth, Incidence problems in the Euclidean space, Masters Thesis (in Hungarian), Eötvös Lor&225;nd University, Budapest, 1997.

Cited By

View all
  • (2022)Point-hyperplane Incidence Geometry and the Log-rank ConjectureACM Transactions on Computation Theory10.1145/354368414:2(1-16)Online publication date: 14-Sep-2022
  • (2022)Nondegenerate Spheres in Four DimensionsDiscrete & Computational Geometry10.1007/s00454-021-00366-568:2(406-424)Online publication date: 14-Jun-2022
  • (2021)Sphere tangencies, line incidences and Lie’s line-sphere correspondenceMathematical Proceedings of the Cambridge Philosophical Society10.1017/S0305004121000256(1-21)Online publication date: 24-Mar-2021
  • Show More Cited By

Index Terms

  1. Incidences of not-too-degenerate hyperplanes

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry
    June 2005
    398 pages
    ISBN:1581139918
    DOI:10.1145/1064092
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 06 June 2005

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Szemerédi-Trotter theorem
    2. incidences

    Qualifiers

    • Article

    Conference

    SoCG05

    Acceptance Rates

    SCG '05 Paper Acceptance Rate 41 of 141 submissions, 29%;
    Overall Acceptance Rate 625 of 1,685 submissions, 37%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)15
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 17 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2022)Point-hyperplane Incidence Geometry and the Log-rank ConjectureACM Transactions on Computation Theory10.1145/354368414:2(1-16)Online publication date: 14-Sep-2022
    • (2022)Nondegenerate Spheres in Four DimensionsDiscrete & Computational Geometry10.1007/s00454-021-00366-568:2(406-424)Online publication date: 14-Jun-2022
    • (2021)Sphere tangencies, line incidences and Lie’s line-sphere correspondenceMathematical Proceedings of the Cambridge Philosophical Society10.1017/S0305004121000256(1-21)Online publication date: 24-Mar-2021
    • (2020)On a theorem of Hegyvári and HennecartPacific Journal of Mathematics10.2140/pjm.2020.305.407305:2(407-421)Online publication date: 29-Apr-2020
    • (2020)An Energy Bound in the Affine GroupInternational Mathematics Research Notices10.1093/imrn/rnaa130Online publication date: 3-Jun-2020
    • (2020)Two theorems on point-flat incidencesComputational Geometry10.1016/j.comgeo.2020.101681(101681)Online publication date: Jun-2020
    • (2018)A note on the size of the set $$\varvec{A^2+A}$$ A 2 + AThe Ramanujan Journal10.1007/s11139-017-9968-446:2(357-372)Online publication date: 9-Feb-2018
    • (2017)Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distancesProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039849(2456-2475)Online publication date: 16-Jan-2017
    • (2017)Expansion for cubes in the Heisenberg groupForum Mathematicum10.1515/forum-2015-023030:1(227-236)Online publication date: 17-Jun-2017
    • (2016)General position subsets and independent hyperplanes in d-spaceJournal of Geometry10.1007/s00022-016-0323-5108:1(33-43)Online publication date: 11-Mar-2016
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media