---
_id: '3514'
abstract:
- lang: eng
  text: We consider the problem of obtaining sharp (nearly quadratic) bounds for the
    combinatorial complexity of the lower envelope (i.e. pointwise minimum) of a collection
    of n bivariate (or generally multi-variate) continuous and "simple"
    functions, and of designing efficient algorithms for the calculation of this envelope.
    This problem generalizes the well-studied univariate case (whose analysis is based
    on the theory of Davenport-Schinzel sequences), but appears to be much more difficult
    and still largely unsolved. It is a central problem that arises in many areas
    in computational and combinatorial geometry, and has numerous applications including
    generalized planar Voronoi diagrams, hidden surface elimination for intersecting
    surfaces, purely translational motion planning, finding common transversals of
    polyhedra, and more. In this abstract we provide several partial solutions and
    generalizations of this problem, and apply them to the problems mentioned above.
    The most significant of our results is that the lower envelope of n triangles
    in three dimensions has combinatorial complexity at most O(n2α(n)) (where α(n)
    is the extremely slowly growing inverse of Ackermann's function), that this bound
    is tight in the worst case, and that this envelope can be calculated in time O(n2α(n)).
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: János
  full_name: Pach, János
  last_name: Pach
- first_name: Jacob
  full_name: Schwartz, Jacob
  last_name: Schwartz
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: 'Edelsbrunner H, Pach J, Schwartz J, Sharir M. On the lower envelope of bivariate
    functions and its applications. In: <i>28th Annual Symposium on Foundations of
    Computer Science </i>. IEEE; 1987:27-37. doi:<a href="https://doi.org/10.1109/SFCS.1987.44">10.1109/SFCS.1987.44</a>'
  apa: 'Edelsbrunner, H., Pach, J., Schwartz, J., &#38; Sharir, M. (1987). On the
    lower envelope of bivariate functions and its applications. In <i>28th Annual
    Symposium on Foundations of Computer Science </i> (pp. 27–37). Los Angeles, CA,
    USA: IEEE. <a href="https://doi.org/10.1109/SFCS.1987.44">https://doi.org/10.1109/SFCS.1987.44</a>'
  chicago: Edelsbrunner, Herbert, János Pach, Jacob Schwartz, and Micha Sharir. “On
    the Lower Envelope of Bivariate Functions and Its Applications.” In <i>28th Annual
    Symposium on Foundations of Computer Science </i>, 27–37. IEEE, 1987. <a href="https://doi.org/10.1109/SFCS.1987.44">https://doi.org/10.1109/SFCS.1987.44</a>.
  ieee: H. Edelsbrunner, J. Pach, J. Schwartz, and M. Sharir, “On the lower envelope
    of bivariate functions and its applications,” in <i>28th Annual Symposium on Foundations
    of Computer Science </i>, Los Angeles, CA, USA, 1987, pp. 27–37.
  ista: 'Edelsbrunner H, Pach J, Schwartz J, Sharir M. 1987. On the lower envelope
    of bivariate functions and its applications. 28th Annual Symposium on Foundations
    of Computer Science . FOCS: Foundations of Computer Science, 27–37.'
  mla: Edelsbrunner, Herbert, et al. “On the Lower Envelope of Bivariate Functions
    and Its Applications.” <i>28th Annual Symposium on Foundations of Computer Science
    </i>, IEEE, 1987, pp. 27–37, doi:<a href="https://doi.org/10.1109/SFCS.1987.44">10.1109/SFCS.1987.44</a>.
  short: H. Edelsbrunner, J. Pach, J. Schwartz, M. Sharir, in:, 28th Annual Symposium
    on Foundations of Computer Science , IEEE, 1987, pp. 27–37.
conference:
  end_date: 1987-10-14
  location: Los Angeles, CA, USA
  name: 'FOCS: Foundations of Computer Science'
  start_date: 1987-10-12
date_created: 2018-12-11T12:03:44Z
date_published: 1987-10-14T00:00:00Z
date_updated: 2022-02-07T15:14:55Z
day: '14'
doi: 10.1109/SFCS.1987.44
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/document/4568253?denied=
month: '10'
oa_version: None
page: 27 - 37
publication: '28th Annual Symposium on Foundations of Computer Science '
publication_identifier:
  isbn:
  - 0-8186-0807-2
  issn:
  - 0272-5428
publication_status: published
publisher: IEEE
publist_id: '2871'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the lower envelope of bivariate functions and its applications
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1987'
...