---
_id: '4049'
abstract:
- lang: eng
  text: The edge-insertion paradigm improves a triangulation of a finite point set
    in R2 iteratively by adding a new edge, deleting intersecting old edges, and retriangulating
    the resulting two polygonal regions. After presenting an abstract view of the
    paradigm, this paper shows that it can be used to obtain polynomial time algorithms
    for several types of optimal triangulations.
acknowledgement: Research of the second author is supported by the National Science
  Foundation under grant no. CCR-8921421 and under the Alan T. Waterman award, grant
  no. CCR-9118874. Any opinions, finding and conclusions or recommendations expressed
  in this publication are those of the authors and do not necessarily reflect the
  view of the National Science Foundation. Part of the work was done while the second,
  third, and fourth authors visited the Xerox Palo Alto Research Center. The fifth
  author is on study leave from the National University of Singapore, Republic of
  Singapore.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Marshall
  full_name: Bern, Marshall
  last_name: Bern
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: David
  full_name: Eppstein, David
  last_name: Eppstein
- first_name: Stephen
  full_name: Mitchell, Stephen
  last_name: Mitchell
- first_name: Tiow
  full_name: Tan, Tiow
  last_name: Tan
citation:
  ama: 'Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. Edge insertion for
    optimal triangulations. In: Simon I, ed. <i>1st Latin American Symposium on Theoretical
    Informatics</i>. Vol 583. Springer; 1992:46-60. doi:<a href="https://doi.org/10.1007/BFb0023816">10.1007/BFb0023816</a>'
  apa: 'Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., &#38; Tan, T. (1992).
    Edge insertion for optimal triangulations. In I. Simon (Ed.), <i>1st Latin American
    Symposium on Theoretical Informatics</i> (Vol. 583, pp. 46–60). São Paulo, Brazil:
    Springer. <a href="https://doi.org/10.1007/BFb0023816">https://doi.org/10.1007/BFb0023816</a>'
  chicago: Bern, Marshall, Herbert Edelsbrunner, David Eppstein, Stephen Mitchell,
    and Tiow Tan. “Edge Insertion for Optimal Triangulations.” In <i>1st Latin American
    Symposium on Theoretical Informatics</i>, edited by Imre Simon, 583:46–60. Springer,
    1992. <a href="https://doi.org/10.1007/BFb0023816">https://doi.org/10.1007/BFb0023816</a>.
  ieee: M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T. Tan, “Edge insertion
    for optimal triangulations,” in <i>1st Latin American Symposium on Theoretical
    Informatics</i>, São Paulo, Brazil, 1992, vol. 583, pp. 46–60.
  ista: 'Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. 1992. Edge insertion
    for optimal triangulations. 1st Latin American Symposium on Theoretical Informatics.
    LATIN: Latin American Symposium on Theoretical Informatics , LNCS, vol. 583, 46–60.'
  mla: Bern, Marshall, et al. “Edge Insertion for Optimal Triangulations.” <i>1st
    Latin American Symposium on Theoretical Informatics</i>, edited by Imre Simon,
    vol. 583, Springer, 1992, pp. 46–60, doi:<a href="https://doi.org/10.1007/BFb0023816">10.1007/BFb0023816</a>.
  short: M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, T. Tan, in:, I. Simon
    (Ed.), 1st Latin American Symposium on Theoretical Informatics, Springer, 1992,
    pp. 46–60.
conference:
  end_date: 1992-04-10
  location: São Paulo, Brazil
  name: 'LATIN: Latin American Symposium on Theoretical Informatics '
  start_date: 1992-04-06
date_created: 2018-12-11T12:06:38Z
date_published: 1992-04-07T00:00:00Z
date_updated: 2022-03-16T08:04:53Z
day: '07'
doi: 10.1007/BFb0023816
editor:
- first_name: Imre
  full_name: Simon, Imre
  last_name: Simon
extern: '1'
intvolume: '       583'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/BFb0023816
month: '04'
oa_version: None
page: 46 - 60
publication: 1st Latin American Symposium on Theoretical Informatics
publication_identifier:
  isbn:
  - 978-3-540-55284-0
publication_status: published
publisher: Springer
publist_id: '2076'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Edge insertion for optimal triangulations
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 583
year: '1992'
...