---
_id: '3566'
abstract:
- lang: eng
  text: This paper proves an O(m2/3n2/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. © Springer-Verlag Berlin Heidelberg 1990.
alternative_title:
- DIMACS Series in Discrete Mathematics and Theoretical Computer Science
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>Applied Geometry and Discrete Mathematics: The Victor
    Klee Festschrift</i>. Vol 4. American Mathematical Society; 1991:253-263.'
  apa: 'Edelsbrunner, H., &#38; Sharir, M. (1991). A hyperplane incidence problem
    with applications to counting distances. In <i>Applied Geometry and Discrete Mathematics:
    The Victor Klee Festschrift</i> (Vol. 4, pp. 253–263). American Mathematical Society.'
  chicago: 'Edelsbrunner, Herbert, and Micha Sharir. “A Hyperplane Incidence Problem
    with Applications to Counting Distances.” In <i>Applied Geometry and Discrete
    Mathematics: The Victor Klee Festschrift</i>, 4:253–63. American Mathematical
    Society, 1991.'
  ieee: 'H. Edelsbrunner and M. Sharir, “A hyperplane incidence problem with applications
    to counting distances,” in <i>Applied Geometry and Discrete Mathematics: The Victor
    Klee Festschrift</i>, vol. 4, American Mathematical Society, 1991, pp. 253–263.'
  ista: 'Edelsbrunner H, Sharir M. 1991.A hyperplane incidence problem with applications
    to counting distances. In: Applied Geometry and Discrete Mathematics: The Victor
    Klee Festschrift. DIMACS Series in Discrete Mathematics and Theoretical Computer
    Science, vol. 4, 253–263.'
  mla: 'Edelsbrunner, Herbert, and Micha Sharir. “A Hyperplane Incidence Problem with
    Applications to Counting Distances.” <i>Applied Geometry and Discrete Mathematics:
    The Victor Klee Festschrift</i>, vol. 4, American Mathematical Society, 1991,
    pp. 253–63.'
  short: 'H. Edelsbrunner, M. Sharir, in:, Applied Geometry and Discrete Mathematics:
    The Victor Klee Festschrift, American Mathematical Society, 1991, pp. 253–263.'
date_created: 2018-12-11T12:04:00Z
date_published: 1991-04-01T00:00:00Z
date_updated: 2022-03-03T13:27:01Z
day: '01'
extern: '1'
intvolume: '         4'
language:
- iso: eng
main_file_link:
- url: http://www.cs.duke.edu/~edels/Papers/1991-B-01-HyperplaneIncidence.pdf
month: '04'
oa_version: None
page: 253 - 263
publication: 'Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift'
publication_identifier:
  isbn:
  - 978-0897913850
publication_status: published
publisher: American Mathematical Society
publist_id: '2819'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A hyperplane incidence problem with applications to counting distances
type: book_chapter
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1991'
...