---
_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: <i>Proceedings of the 6th Annual Symposium on
    Computational Geometry</i>. ACM; 1990:44-52. doi:<a href="https://doi.org/10.1145/98524.98535">10.1145/98524.98535</a>'
  apa: 'Edelsbrunner, H., Tan, T., &#38; Waupotitsch, R. (1990). An O(n^2log n) time
    algorithm for the MinMax angle triangulation. In <i>Proceedings of the 6th annual
    symposium on Computational geometry</i> (pp. 44–52). Berkley, CA, United States:
    ACM. <a href="https://doi.org/10.1145/98524.98535">https://doi.org/10.1145/98524.98535</a>'
  chicago: Edelsbrunner, Herbert, Tiow Tan, and Roman Waupotitsch. “An O(N^2log n)
    Time Algorithm for the MinMax Angle Triangulation.” In <i>Proceedings of the 6th
    Annual Symposium on Computational Geometry</i>, 44–52. ACM, 1990. <a href="https://doi.org/10.1145/98524.98535">https://doi.org/10.1145/98524.98535</a>.
  ieee: H. Edelsbrunner, T. Tan, and R. Waupotitsch, “An O(n^2log n) time algorithm
    for the MinMax angle triangulation,” in <i>Proceedings of the 6th annual symposium
    on Computational geometry</i>, 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.” <i>Proceedings of the 6th Annual Symposium on Computational
    Geometry</i>, ACM, 1990, pp. 44–52, doi:<a href="https://doi.org/10.1145/98524.98535">10.1145/98524.98535</a>.
  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'
...
---
_id: '4076'
abstract:
- lang: eng
  text: We present an algorithm to compute a Euclidean minimum spanning tree of a
    given set S of n points in Ed in time O(Td(N, N) logd N), where Td(n, m) is the
    time required to compute a bichromatic closest pair among n red and m blue points
    in Ed. If Td(N, N) = Ω(N1+ε), for some fixed ε &gt; 0, then the running time improves
    to O(Td(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic
    closets pair in expected time O((nm log n log m)2/3+m log2 n + n log2 m) in E3,
    which yields an O(N4/3log4/3 N) expected time algorithm for computing a Euclidean
    minimum spanning tree of N points in E3.
article_processing_charge: No
author:
- first_name: Pankaj
  full_name: Agarwal, Pankaj
  last_name: Agarwal
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Otfried
  full_name: Schwarzkopf, Otfried
  last_name: Schwarzkopf
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: 'Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E.  Euclidean minimum spanning
    trees and bichromatic closest pairs. In: <i>Proceedings of the 6th Annual Symposium
    on Computational Geometry</i>. ACM; 1990:203-210. doi:<a href="https://doi.org/10.1145/98524.98567">10.1145/98524.98567</a>'
  apa: 'Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., &#38; Welzl, E. (1990).  Euclidean
    minimum spanning trees and bichromatic closest pairs. In <i>Proceedings of the
    6th annual symposium on Computational geometry</i> (pp. 203–210). Berkeley, CA,
    United States: ACM. <a href="https://doi.org/10.1145/98524.98567">https://doi.org/10.1145/98524.98567</a>'
  chicago: Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl.
    “ Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” In <i>Proceedings
    of the 6th Annual Symposium on Computational Geometry</i>, 203–10. ACM, 1990.
    <a href="https://doi.org/10.1145/98524.98567">https://doi.org/10.1145/98524.98567</a>.
  ieee: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “ Euclidean minimum
    spanning trees and bichromatic closest pairs,” in <i>Proceedings of the 6th annual
    symposium on Computational geometry</i>, Berkeley, CA, United States, 1990, pp.
    203–210.
  ista: 'Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. 1990.  Euclidean minimum
    spanning trees and bichromatic closest pairs. Proceedings of the 6th annual symposium
    on Computational geometry. SCG: Symposium on Computational Geometry, 203–210.'
  mla: Agarwal, Pankaj, et al. “ Euclidean Minimum Spanning Trees and Bichromatic
    Closest Pairs.” <i>Proceedings of the 6th Annual Symposium on Computational Geometry</i>,
    ACM, 1990, pp. 203–10, doi:<a href="https://doi.org/10.1145/98524.98567">10.1145/98524.98567</a>.
  short: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, in:, Proceedings of
    the 6th Annual Symposium on Computational Geometry, ACM, 1990, pp. 203–210.
conference:
  end_date: 1990-06-09
  location: Berkeley, CA, United States
  name: 'SCG: Symposium on Computational Geometry'
  start_date: 1990-06-07
date_created: 2018-12-11T12:06:48Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-16T15:30:22Z
day: '01'
doi: 10.1145/98524.98567
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98567
month: '01'
oa_version: None
page: 203 - 210
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: '2044'
quality_controlled: '1'
scopus_import: '1'
status: public
title: ' Euclidean minimum spanning trees and bichromatic closest pairs'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...
---
_id: '4077'
abstract:
- lang: eng
  text: We prove that for any set S of n points in the plane and n3-α triangles spanned
    by the points of S there exists a point (not necessarily of S) contained in at
    least n3-3α/(512 log25 n) of the triangles. This implies that any set of n points
    in three - dimensional space defines at most 6.4n8/3 log5/3 n halving planes.
article_processing_charge: No
author:
- first_name: Boris
  full_name: Aronov, Boris
  last_name: Aronov
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- 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
- first_name: Rephael
  full_name: Wenger, Rephael
  last_name: Wenger
citation:
  ama: 'Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. Points
    and triangles in the plane and halving planes in space. In: <i>Proceedings of
    the 6th Annual Symposium on Computational Geometry</i>. ACM; 1990:112-115. doi:<a
    href="https://doi.org/10.1145/98524.98548">10.1145/98524.98548</a>'
  apa: 'Aronov, B., Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &#38;
    Wenger, R. (1990). Points and triangles in the plane and halving planes in space.
    In <i>Proceedings of the 6th annual symposium on Computational geometry</i> (pp.
    112–115). Berkley, CA, United States: ACM. <a href="https://doi.org/10.1145/98524.98548">https://doi.org/10.1145/98524.98548</a>'
  chicago: Aronov, Boris, Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas,
    Micha Sharir, and Rephael Wenger. “Points and Triangles in the Plane and Halving
    Planes in Space.” In <i>Proceedings of the 6th Annual Symposium on Computational
    Geometry</i>, 112–15. ACM, 1990. <a href="https://doi.org/10.1145/98524.98548">https://doi.org/10.1145/98524.98548</a>.
  ieee: B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and R. Wenger,
    “Points and triangles in the plane and halving planes in space,” in <i>Proceedings
    of the 6th annual symposium on Computational geometry</i>, Berkley, CA, United
    States, 1990, pp. 112–115.
  ista: 'Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. 1990.
    Points and triangles in the plane and halving planes in space. Proceedings of
    the 6th annual symposium on Computational geometry. SCG: Symposium on Computational
    Geometry, 112–115.'
  mla: Aronov, Boris, et al. “Points and Triangles in the Plane and Halving Planes
    in Space.” <i>Proceedings of the 6th Annual Symposium on Computational Geometry</i>,
    ACM, 1990, pp. 112–15, doi:<a href="https://doi.org/10.1145/98524.98548">10.1145/98524.98548</a>.
  short: B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, R. Wenger,
    in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990,
    pp. 112–115.
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:48Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-17T09:42:27Z
day: '01'
doi: 10.1145/98524.98548
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98548
month: '01'
oa_version: None
page: 112 - 115
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: '2045'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Points and triangles in the plane and halving planes in space
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...
---
_id: '4078'
abstract:
- lang: eng
  text: In this paper we derived combinatorial point selection results for geometric
    objects defined by pairs of points. In a nutshell, the results say that if many
    pairs of a set of n points in some fixed dimension each define a geometric object
    of some type, then there is a point covered by many of these objects. Based on
    such a result for three-dimensional spheres we show that the combinatorial size
    of the Delaunay triangulation of a point set in space can be reduced by adding
    new points. We believe that from a practical point of view this is the most important
    result of this paper.
article_processing_charge: No
author:
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- 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: John
  full_name: Hershberger, John
  last_name: Hershberger
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: 'Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. Slimming
    down by adding; selecting heavily covered points. In: <i>Proceedings of the 6th
    Annual Symposium on Computational Geometry</i>. ACM; 1990:116-127. doi:<a href="https://doi.org/10.1145/98524.98551">10.1145/98524.98551</a>'
  apa: 'Chazelle, B., Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., &#38;
    Sharir, M. (1990). Slimming down by adding; selecting heavily covered points.
    In <i>Proceedings of the 6th annual symposium on computational geometry</i> (pp.
    116–127). Berkley, CA, United States: ACM. <a href="https://doi.org/10.1145/98524.98551">https://doi.org/10.1145/98524.98551</a>'
  chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, John Hershberger,
    Raimund Seidel, and Micha Sharir. “Slimming down by Adding; Selecting Heavily
    Covered Points.” In <i>Proceedings of the 6th Annual Symposium on Computational
    Geometry</i>, 116–27. ACM, 1990. <a href="https://doi.org/10.1145/98524.98551">https://doi.org/10.1145/98524.98551</a>.
  ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, and M.
    Sharir, “Slimming down by adding; selecting heavily covered points,” in <i>Proceedings
    of the 6th annual symposium on computational geometry</i>, Berkley, CA, United
    States, 1990, pp. 116–127.
  ista: 'Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M.
    1990. Slimming down by adding; selecting heavily covered points. Proceedings of
    the 6th annual symposium on computational geometry. SCG: Symposium on Computational
    Geometry, 116–127.'
  mla: Chazelle, Bernard, et al. “Slimming down by Adding; Selecting Heavily Covered
    Points.” <i>Proceedings of the 6th Annual Symposium on Computational Geometry</i>,
    ACM, 1990, pp. 116–27, doi:<a href="https://doi.org/10.1145/98524.98551">10.1145/98524.98551</a>.
  short: B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir,
    in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990,
    pp. 116–127.
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:48Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-17T10:09:54Z
day: '01'
doi: 10.1145/98524.98551
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/98524.98551
month: '01'
oa_version: None
page: 116 - 127
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: '2046'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Slimming down by adding; selecting heavily covered points
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...