---
_id: '4067'
abstract:
- lang: eng
  text: This paper proves an O(m 2/3 n 2/3+m+n) upper bound on the number of incidences
    between m points and n hyperplanes in four dimensions, assuming all points lie
    on one side of each hyperplane and the points and hyperplanes satisfy certain
    natural general position conditions. This result has application to various three-dimensional
    combinatorial distance problems. For example, it implies the same upper bound
    for the number of bichromatic minimum distance pairs in a set of m blue and n
    red points in three-dimensional space. This improves the best previous bound for
    this problem.
acknowledgement: Research of the first author was supported by the National Science
  Foundation under grant CCR-8714565. Work of the second author was supported by Office
  of Naval Research Grants DCR-83-20085 and CCR-89-01484, and by grants from the U.S.-Israeli
  Binational Science Foundation, the NCRD — the Israeli National Council for Research
  and Development, and the Fund for Basic Research in Electronics, Computers and Communication
  administered by the Israeli Academy of Sciences.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: 'Edelsbrunner H, Sharir M. A hyperplane Incidence problem with applications
    to counting distances. In: <i>Proceedings of the International Symposium on Algorithms</i>.
    Vol 450. Springer; 1990:419-428. doi:<a href="https://doi.org/10.1007/3-540-52921-7_91">10.1007/3-540-52921-7_91</a>'
  apa: 'Edelsbrunner, H., &#38; Sharir, M. (1990). A hyperplane Incidence problem
    with applications to counting distances. In <i>Proceedings of the International
    Symposium on Algorithms</i> (Vol. 450, pp. 419–428). Tokyo, Japan: Springer. <a
    href="https://doi.org/10.1007/3-540-52921-7_91">https://doi.org/10.1007/3-540-52921-7_91</a>'
  chicago: Edelsbrunner, Herbert, and Micha Sharir. “A Hyperplane Incidence Problem
    with Applications to Counting Distances.” In <i>Proceedings of the International
    Symposium on Algorithms</i>, 450:419–28. Springer, 1990. <a href="https://doi.org/10.1007/3-540-52921-7_91">https://doi.org/10.1007/3-540-52921-7_91</a>.
  ieee: H. Edelsbrunner and M. Sharir, “A hyperplane Incidence problem with applications
    to counting distances,” in <i>Proceedings of the International Symposium on Algorithms</i>,
    Tokyo, Japan, 1990, vol. 450, pp. 419–428.
  ista: Edelsbrunner H, Sharir M. 1990. A hyperplane Incidence problem with applications
    to counting distances. Proceedings of the International Symposium on Algorithms.
    SIGAL:  Special Interest Group on Algorithms, International Symposium on Algorithms 
    , LNCS, vol. 450, 419–428.
  mla: Edelsbrunner, Herbert, and Micha Sharir. “A Hyperplane Incidence Problem with
    Applications to Counting Distances.” <i>Proceedings of the International Symposium
    on Algorithms</i>, vol. 450, Springer, 1990, pp. 419–28, doi:<a href="https://doi.org/10.1007/3-540-52921-7_91">10.1007/3-540-52921-7_91</a>.
  short: H. Edelsbrunner, M. Sharir, in:, Proceedings of the International Symposium
    on Algorithms, Springer, 1990, pp. 419–428.
conference:
  end_date: 1990-08-18
  location: Tokyo, Japan
  name: 'SIGAL:  Special Interest Group on Algorithms, International Symposium on
    Algorithms  '
  start_date: 1990-08-16
date_created: 2018-12-11T12:06:45Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T14:31:26Z
day: '01'
doi: 10.1007/3-540-52921-7_91
extern: '1'
intvolume: '       450'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-52921-7_91
month: '01'
oa_version: None
page: 419 - 428
publication: Proceedings of the International Symposium on Algorithms
publication_identifier:
  isbn:
  - 978-3-540-52921-7
publication_status: published
publisher: Springer
publist_id: '2056'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A hyperplane Incidence problem with applications to counting distances
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 450
year: '1990'
...