---
_id: '4081'
abstract:
- lang: eng
  text: This paper studies applications of envelopes of piecewise linear functions
    to problems in computational geometry. Among these applications we find problems
    involving hidden line/surface elimination, motion planning, transversals of polytopes,
    and a new type of Voronoi diagram for clusters of points. All results are either
    combinatorial or computational in nature. They are based on the combinatorial
    analysis in two companion papers [PS] and [E2] and a divide-and-conquer algorithm
    for computing envelopes described in this paper.
acknowledgement: Work on this paper by the first author has been supported by Amoco
  Fnd. Fac. Dev. Comput. Sci. 1-6-44862. Work by the third author has been supported
  by the Office of Naval Research Grant N00014-82-K-0381, National Science Foundation
  Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and
  the IBM Corporation, and by a research grant from NCRD, the Israeli National Council
  for Research and Development.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: 'Edelsbrunner H, Guibas L, Sharir M. The upper envelope of piecewise linear
    functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>.
    1989;4(1):311-336. doi:<a href="https://doi.org/10.1007/BF02187733">10.1007/BF02187733</a>'
  apa: 'Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1989). The upper envelope
    of piecewise linear functions: Algorithms and applications. <i>Discrete &#38;
    Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187733">https://doi.org/10.1007/BF02187733</a>'
  chicago: 'Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Upper Envelope
    of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38;
    Computational Geometry</i>. Springer, 1989. <a href="https://doi.org/10.1007/BF02187733">https://doi.org/10.1007/BF02187733</a>.'
  ieee: 'H. Edelsbrunner, L. Guibas, and M. Sharir, “The upper envelope of piecewise
    linear functions: Algorithms and applications,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 4, no. 1. Springer, pp. 311–336, 1989.'
  ista: 'Edelsbrunner H, Guibas L, Sharir M. 1989. The upper envelope of piecewise
    linear functions: Algorithms and applications. Discrete &#38; Computational Geometry.
    4(1), 311–336.'
  mla: 'Edelsbrunner, Herbert, et al. “The Upper Envelope of Piecewise Linear Functions:
    Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>, vol.
    4, no. 1, Springer, 1989, pp. 311–36, doi:<a href="https://doi.org/10.1007/BF02187733">10.1007/BF02187733</a>.'
  short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry
    4 (1989) 311–336.
date_created: 2018-12-11T12:06:50Z
date_published: 1989-12-01T00:00:00Z
date_updated: 2022-02-10T15:53:48Z
day: '01'
doi: 10.1007/BF02187733
extern: '1'
intvolume: '         4'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://link.springer.com/article/10.1007/BF02187733
month: '12'
oa: 1
oa_version: Published Version
page: 311 - 336
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2038'
quality_controlled: '1'
status: public
title: 'The upper envelope of piecewise linear functions: Algorithms and applications'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1989'
...