[{"author":[{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"last_name":"Tan","full_name":"Tan, Tiow","first_name":"Tiow"},{"full_name":"Waupotitsch, Roman","last_name":"Waupotitsch","first_name":"Roman"}],"doi":"10.1145/98524.98535","day":"01","article_processing_charge":"No","oa_version":"None","publisher":"ACM","title":"An O(n^2log n) time algorithm for the MinMax angle triangulation","date_updated":"2022-02-22T08:56:42Z","_id":"4071","type":"conference","date_created":"2018-12-11T12:06:46Z","page":"44 - 52","abstract":[{"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.","lang":"eng"}],"main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/98524.98535"}],"publication_identifier":{"isbn":["978-0-89791-362-1"]},"quality_controlled":"1","publication_status":"published","year":"1990","month":"01","publist_id":"2052","language":[{"iso":"eng"}],"status":"public","publication":"Proceedings of the 6th annual symposium on Computational geometry","extern":"1","citation":{"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.","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>.","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>","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>.","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>","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.","short":"H. Edelsbrunner, T. Tan, R. Waupotitsch, in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990, pp. 44–52."},"date_published":"1990-01-01T00:00:00Z","conference":{"name":"SCG: Symposium on Computational Geometry","end_date":"1990-06-09","start_date":"1990-06-07","location":"Berkley, CA, United States"},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"},{"conference":{"start_date":"1990-06-07","end_date":"1990-06-09","name":"SCG: Symposium on Computational Geometry","location":"Berkeley, CA, United States"},"date_published":"1990-01-01T00:00:00Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","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>","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.","short":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990, pp. 203–210.","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>.","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.","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>","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>."},"publication":"Proceedings of the 6th annual symposium on Computational geometry","status":"public","extern":"1","language":[{"iso":"eng"}],"publist_id":"2044","month":"01","year":"1990","quality_controlled":"1","publication_status":"published","publication_identifier":{"isbn":["978-0-89791-362-1"]},"main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/98524.98567"}],"abstract":[{"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.","lang":"eng"}],"page":"203 - 210","type":"conference","date_created":"2018-12-11T12:06:48Z","date_updated":"2022-02-16T15:30:22Z","_id":"4076","oa_version":"None","title":" Euclidean minimum spanning trees and bichromatic closest pairs","publisher":"ACM","author":[{"first_name":"Pankaj","last_name":"Agarwal","full_name":"Agarwal, Pankaj"},{"last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","orcid":"0000-0002-9823-6833"},{"first_name":"Otfried","last_name":"Schwarzkopf","full_name":"Schwarzkopf, Otfried"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"doi":"10.1145/98524.98567","day":"01","scopus_import":"1","article_processing_charge":"No"},{"publication_identifier":{"isbn":["978-0-89791-362-1"]},"quality_controlled":"1","publication_status":"published","main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/98524.98548"}],"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."}],"page":"112 - 115","type":"conference","date_created":"2018-12-11T12:06:48Z","date_updated":"2022-02-17T09:42:27Z","_id":"4077","oa_version":"None","publisher":"ACM","title":"Points and triangles in the plane and halving planes in space","author":[{"first_name":"Boris","full_name":"Aronov, Boris","last_name":"Aronov"},{"first_name":"Bernard","full_name":"Chazelle, Bernard","last_name":"Chazelle"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"last_name":"Sharir","full_name":"Sharir, Micha","first_name":"Micha"},{"full_name":"Wenger, Rephael","last_name":"Wenger","first_name":"Rephael"}],"doi":"10.1145/98524.98548","article_processing_charge":"No","scopus_import":"1","day":"01","conference":{"start_date":"1990-06-07","end_date":"1990-06-09","name":"SCG: Symposium on Computational Geometry","location":"Berkley, CA, United States"},"date_published":"1990-01-01T00:00:00Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","citation":{"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.","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.","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>","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>.","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>.","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."},"status":"public","language":[{"iso":"eng"}],"publication":"Proceedings of the 6th annual symposium on Computational geometry","extern":"1","publist_id":"2045","month":"01","year":"1990"},{"publist_id":"2046","year":"1990","month":"01","citation":{"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.","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>.","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>.","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>","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>","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.","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."},"conference":{"end_date":"1990-06-09","start_date":"1990-06-07","name":"SCG: Symposium on Computational Geometry","location":"Berkley, CA, United States"},"date_published":"1990-01-01T00:00:00Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","language":[{"iso":"eng"}],"status":"public","publication":"Proceedings of the 6th annual symposium on computational geometry","extern":"1","date_updated":"2022-02-17T10:09:54Z","_id":"4078","type":"conference","date_created":"2018-12-11T12:06:48Z","doi":"10.1145/98524.98551","author":[{"last_name":"Chazelle","full_name":"Chazelle, Bernard","first_name":"Bernard"},{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"full_name":"Hershberger, John","last_name":"Hershberger","first_name":"John"},{"first_name":"Raimund","full_name":"Seidel, Raimund","last_name":"Seidel"},{"last_name":"Sharir","full_name":"Sharir, Micha","first_name":"Micha"}],"day":"01","article_processing_charge":"No","scopus_import":"1","title":"Slimming down by adding; selecting heavily covered points","publisher":"ACM","oa_version":"None","main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/98524.98551"}],"quality_controlled":"1","publication_status":"published","publication_identifier":{"isbn":["978-0-89791-362-1"]},"page":"116 - 127","abstract":[{"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.","lang":"eng"}]}]