---
_id: '4071'
abstract:
- lang: eng
text: We show that a triangulation of a set of n points in the plane that minimizes
the maximum angle can be computed in time O(n2 log n) and space O(n). In the same
amount of time and space we can also handle the constrained case where edges are
prescribed. The algorithm iteratively improves an arbitrary initial triangulation
and is fairly easy to implement.
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: Tiow
full_name: Tan, Tiow
last_name: Tan
- first_name: Roman
full_name: Waupotitsch, Roman
last_name: Waupotitsch
citation:
ama: 'Edelsbrunner H, Tan T, Waupotitsch R. An O(n^2log n) time algorithm for the
MinMax angle triangulation. In: Proceedings of the 6th Annual Symposium on
Computational Geometry. ACM; 1990:44-52. doi:10.1145/98524.98535'
apa: 'Edelsbrunner, H., Tan, T., & Waupotitsch, R. (1990). An O(n^2log n) time
algorithm for the MinMax angle triangulation. In Proceedings of the 6th annual
symposium on Computational geometry (pp. 44–52). Berkley, CA, United States:
ACM. https://doi.org/10.1145/98524.98535'
chicago: Edelsbrunner, Herbert, Tiow Tan, and Roman Waupotitsch. “An O(N^2log n)
Time Algorithm for the MinMax Angle Triangulation.” In Proceedings of the 6th
Annual Symposium on Computational Geometry, 44–52. ACM, 1990. https://doi.org/10.1145/98524.98535.
ieee: H. Edelsbrunner, T. Tan, and R. Waupotitsch, “An O(n^2log n) time algorithm
for the MinMax angle triangulation,” in Proceedings of the 6th annual symposium
on Computational geometry, Berkley, CA, United States, 1990, pp. 44–52.
ista: 'Edelsbrunner H, Tan T, Waupotitsch R. 1990. An O(n^2log n) time algorithm
for the MinMax angle triangulation. Proceedings of the 6th annual symposium on
Computational geometry. SCG: Symposium on Computational Geometry, 44–52.'
mla: Edelsbrunner, Herbert, et al. “An O(N^2log n) Time Algorithm for the MinMax
Angle Triangulation.” Proceedings of the 6th Annual Symposium on Computational
Geometry, ACM, 1990, pp. 44–52, doi:10.1145/98524.98535.
short: H. Edelsbrunner, T. Tan, R. Waupotitsch, in:, Proceedings of the 6th Annual
Symposium on Computational Geometry, ACM, 1990, pp. 44–52.
conference:
end_date: 1990-06-09
location: Berkley, CA, United States
name: 'SCG: Symposium on Computational Geometry'
start_date: 1990-06-07
date_created: 2018-12-11T12:06:46Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-22T08:56:42Z
day: '01'
doi: 10.1145/98524.98535
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98535
month: '01'
oa_version: None
page: 44 - 52
publication: Proceedings of the 6th annual symposium on Computational geometry
publication_identifier:
isbn:
- 978-0-89791-362-1
publication_status: published
publisher: ACM
publist_id: '2052'
quality_controlled: '1'
status: public
title: An O(n^2log n) time algorithm for the MinMax angle triangulation
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...