[{"acknowledgement":"Research of the first author was supported by Amoco Foundation for Faculty Development in Computer Science Grant No. 1-6-44862. Work on this paper by the second author was supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation.","date_published":"1990-01-01T00:00:00Z","page":"35 - 42","publist_id":"2057","extern":1,"abstract":[{"lang":"eng","text":"LetS be a collection ofn convex, closed, and pairwise nonintersecting sets in the Euclidean plane labeled from 1 ton. A pair of permutations\n(i1i2in−1in)(inin−1i2i1) \nis called ageometric permutation of S if there is a line that intersects all sets ofS in this order. We prove thatS can realize at most 2n–2 geometric permutations. This upper bound is tight."}],"year":"1990","author":[{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Herbert Edelsbrunner"},{"last_name":"Sharir","full_name":"Sharir, Micha","first_name":"Micha"}],"type":"journal_article","citation":{"ista":"Edelsbrunner H, Sharir M. 1990. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. Discrete & Computational Geometry. 5(1), 35–42.","apa":"Edelsbrunner, H., & Sharir, M. (1990). The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. *Discrete & Computational Geometry*. Springer. https://doi.org/ 10.1007/BF02187778","mla":"Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” *Discrete & Computational Geometry*, vol. 5, no. 1, Springer, 1990, pp. 35–42, doi: 10.1007/BF02187778.","chicago":"Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” *Discrete & Computational Geometry*. Springer, 1990. https://doi.org/ 10.1007/BF02187778.","short":"H. Edelsbrunner, M. Sharir, Discrete & Computational Geometry 5 (1990) 35–42.","ama":"Edelsbrunner H, Sharir M. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. *Discrete & Computational Geometry*. 1990;5(1):35-42. doi: 10.1007/BF02187778","ieee":"H. Edelsbrunner and M. Sharir, “The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2,” *Discrete & Computational Geometry*, vol. 5, no. 1. Springer, pp. 35–42, 1990."},"day":"01","_id":"4068","month":"01","title":"The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2","publication":"Discrete & Computational Geometry","intvolume":" 5","quality_controlled":0,"status":"public","date_created":"2018-12-11T12:06:45Z","publisher":"Springer","doi":" 10.1007/BF02187778","publication_status":"published","volume":5,"date_updated":"2021-01-12T07:54:16Z","issue":"1"},{"day":"01","month":"01","_id":"4069","title":"An acyclicity theorem for cell complexes in d dimension","intvolume":" 10","publication":"Combinatorica","year":"1990","author":[{"first_name":"Herbert","orcid":"0000-0002-9823-6833","full_name":"Herbert Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner"}],"type":"journal_article","citation":{"chicago":"Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.” *Combinatorica*. Springer, 1990. https://doi.org/10.1007/BF02122779.","ama":"Edelsbrunner H. An acyclicity theorem for cell complexes in d dimension. *Combinatorica*. 1990;10(3):251-260. doi:10.1007/BF02122779","ieee":"H. Edelsbrunner, “An acyclicity theorem for cell complexes in d dimension,” *Combinatorica*, vol. 10, no. 3. Springer, pp. 251–260, 1990.","short":"H. Edelsbrunner, Combinatorica 10 (1990) 251–260.","apa":"Edelsbrunner, H. (1990). An acyclicity theorem for cell complexes in d dimension. *Combinatorica*. Springer. https://doi.org/10.1007/BF02122779","ista":"Edelsbrunner H. 1990. An acyclicity theorem for cell complexes in d dimension. Combinatorica. 10(3), 251–260.","mla":"Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.” *Combinatorica*, vol. 10, no. 3, Springer, 1990, pp. 251–60, doi:10.1007/BF02122779."},"abstract":[{"lang":"eng","text":"Let C be a cell complex in d-dimensional Euclidean space whose faces are obtained by orthogonal projection of the faces of a convex polytope in d + 1 dimensions. For example, the Delaunay triangulation of a finite point set is such a cell complex. This paper shows that the in front/behind relation defined for the faces of C with respect to any fixed viewpoint x is acyclic. This result has applications to hidden line/surface removal and other problems in computational geometry."}],"acknowledgement":"Research reported in this paper was supported by the National Science Foundation under grant CCR-8714565","date_published":"1990-01-01T00:00:00Z","publist_id":"2050","page":"251 - 260","extern":1,"date_updated":"2021-01-12T07:54:16Z","issue":"3","date_created":"2018-12-11T12:06:45Z","publisher":"Springer","doi":"10.1007/BF02122779","publication_status":"published","volume":10,"status":"public","quality_controlled":0},{"quality_controlled":0,"status":"public","date_created":"2018-12-11T12:06:46Z","publisher":"Taylor & Francis","doi":"10.1080/00207169008803871","publication_status":"published","volume":34,"issue":"3-4","date_updated":"2021-01-12T07:54:17Z","date_published":"1990-01-01T00:00:00Z","page":"129 - 144","extern":1,"publist_id":"2051","abstract":[{"text":"Let S be a set of n closed intervals on the x-axis. A ranking assigns to each interval, s, a distinct rank, p(s) [1, 2,…,n]. We say that s can see t if p(s)<p(t) and there is a point ps∩t so that pu for all u with p(s)<p(u)<p(t). It is shown that a ranking can be found in time O(n log n) such that each interval sees at most three other intervals. It is also shown that a ranking that minimizes the average number of endpoints visible from an interval can be computed in time O(n 5/2). The results have applications to intersection problems for intervals, as well as to channel routing problems which arise in layouts of VLSI circuits.","lang":"eng"}],"year":"1990","author":[{"full_name":"Herbert Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833"},{"last_name":"Overmars","full_name":"Overmars, Mark H","first_name":"Mark"},{"last_name":"Welzl","full_name":"Welzl, Emo","first_name":"Emo"},{"first_name":"Irith","last_name":"Hartman","full_name":"Hartman, Irith Ben-Arroyo"},{"first_name":"Jack","last_name":"Feldman","full_name":"Feldman,Jack A"}],"type":"journal_article","citation":{"chicago":"Edelsbrunner, Herbert, Mark Overmars, Emo Welzl, Irith Hartman, and Jack Feldman. “Ranking Intervals under Visibility Constraints.” *International Journal of Computer Mathematics*. Taylor & Francis, 1990. https://doi.org/10.1080/00207169008803871.","short":"H. Edelsbrunner, M. Overmars, E. Welzl, I. Hartman, J. Feldman, International Journal of Computer Mathematics 34 (1990) 129–144.","ieee":"H. Edelsbrunner, M. Overmars, E. Welzl, I. Hartman, and J. Feldman, “Ranking intervals under visibility constraints,” *International Journal of Computer Mathematics*, vol. 34, no. 3–4. Taylor & Francis, pp. 129–144, 1990.","ama":"Edelsbrunner H, Overmars M, Welzl E, Hartman I, Feldman J. Ranking intervals under visibility constraints. *International Journal of Computer Mathematics*. 1990;34(3-4):129-144. doi:10.1080/00207169008803871","apa":"Edelsbrunner, H., Overmars, M., Welzl, E., Hartman, I., & Feldman, J. (1990). Ranking intervals under visibility constraints. *International Journal of Computer Mathematics*. Taylor & Francis. https://doi.org/10.1080/00207169008803871","ista":"Edelsbrunner H, Overmars M, Welzl E, Hartman I, Feldman J. 1990. Ranking intervals under visibility constraints. International Journal of Computer Mathematics. 34(3–4), 129–144.","mla":"Edelsbrunner, Herbert, et al. “Ranking Intervals under Visibility Constraints.” *International Journal of Computer Mathematics*, vol. 34, no. 3–4, Taylor & Francis, 1990, pp. 129–44, doi:10.1080/00207169008803871."},"day":"01","_id":"4070","month":"01","title":"Ranking intervals under visibility constraints","intvolume":" 34","publication":"International Journal of Computer Mathematics"},{"status":"public","quality_controlled":0,"date_updated":"2021-01-12T07:54:18Z","conference":{"name":"SCG: Symposium on Computational Geometry"},"date_created":"2018-12-11T12:06:46Z","publication_status":"published","publisher":"ACM","doi":"10.1145/98524.98535","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."}],"date_published":"1990-01-01T00:00:00Z","publist_id":"2052","page":"44 - 52","extern":1,"day":"01","_id":"4071","month":"01","title":"An O(n^2log n) time algorithm for the MinMax angle triangulation","year":"1990","type":"conference","author":[{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Herbert Edelsbrunner"},{"first_name":"Tiow","last_name":"Tan","full_name":"Tan, Tiow Seng"},{"first_name":"Roman","last_name":"Waupotitsch","full_name":"Waupotitsch, Roman"}],"citation":{"mla":"Edelsbrunner, Herbert, et al. *An O(N^2log n) Time Algorithm for the MinMax Angle Triangulation*. ACM, 1990, pp. 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 (pp. 44–52). Presented at the SCG: Symposium on Computational Geometry, ACM. https://doi.org/10.1145/98524.98535","ista":"Edelsbrunner H, Tan T, Waupotitsch R. 1990. An O(n^2log n) time algorithm for the MinMax angle triangulation. SCG: Symposium on Computational Geometry, 44–52.","ieee":"H. Edelsbrunner, T. Tan, and R. Waupotitsch, “An O(n^2log n) time algorithm for the MinMax angle triangulation,” presented at the SCG: Symposium on Computational Geometry, 1990, pp. 44–52.","short":"H. Edelsbrunner, T. Tan, R. Waupotitsch, in:, ACM, 1990, pp. 44–52.","ama":"Edelsbrunner H, Tan T, Waupotitsch R. An O(n^2log n) time algorithm for the MinMax angle triangulation. In: ACM; 1990:44-52. doi:10.1145/98524.98535","chicago":"Edelsbrunner, Herbert, Tiow Tan, and Roman Waupotitsch. “An O(N^2log n) Time Algorithm for the MinMax Angle Triangulation,” 44–52. ACM, 1990. https://doi.org/10.1145/98524.98535."}},{"publication":"Discrete & Computational Geometry","intvolume":" 5","title":"The complexity and construction of many faces in arrangements of lines and of segments","_id":"4072","month":"01","day":"01","citation":{"ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction of many faces in arrangements of lines and of segments,” *Discrete & Computational Geometry*, vol. 5, no. 1. Springer, pp. 161–196, 1990.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & Computational Geometry 5 (1990) 161–196.","ama":"Edelsbrunner H, Guibas L, Sharir M. The complexity and construction of many faces in arrangements of lines and of segments. *Discrete & Computational Geometry*. 1990;5(1):161-196. doi: 10.1007/BF02187784","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” *Discrete & Computational Geometry*. Springer, 1990. https://doi.org/ 10.1007/BF02187784.","mla":"Edelsbrunner, Herbert, et al. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” *Discrete & Computational Geometry*, vol. 5, no. 1, Springer, 1990, pp. 161–96, doi: 10.1007/BF02187784.","apa":"Edelsbrunner, H., Guibas, L., & Sharir, M. (1990). The complexity and construction of many faces in arrangements of lines and of segments. *Discrete & Computational Geometry*. Springer. https://doi.org/ 10.1007/BF02187784","ista":"Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity and construction of many faces in arrangements of lines and of segments. Discrete & Computational Geometry. 5(1), 161–196."},"type":"journal_article","author":[{"full_name":"Herbert Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833"},{"last_name":"Guibas","full_name":"Guibas, Leonidas J","first_name":"Leonidas"},{"last_name":"Sharir","full_name":"Sharir, Micha","first_name":"Micha"}],"year":"1990","abstract":[{"text":"We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m 2/3– n 2/3+2 +n) for any>0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m 2/3– n 2/3+2 logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m 2/3– n 2/3+2 +n (n) logm) for any>0, where(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m 2/3– n 2/3+2 log+n(n) log2 n logm).","lang":"eng"}],"publist_id":"2053","extern":1,"page":"161 - 196","acknowledgement":"The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation under Grant CCR-8714565. Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD-the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.","date_published":"1990-01-01T00:00:00Z","date_updated":"2021-01-12T07:54:18Z","issue":"1","doi":" 10.1007/BF02187784","publication_status":"published","volume":5,"publisher":"Springer","date_created":"2018-12-11T12:06:46Z","status":"public","quality_controlled":0}]