[{"publication":"Discrete & Computational Geometry","oa_version":"Published Version","month":"12","language":[{"iso":"eng"}],"type":"journal_article","date_published":"1991-12-01T00:00:00Z","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publist_id":"2063","oa":1,"main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02574700"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","scopus_import":"1","_id":"4062","issue":"1","author":[{"full_name":"Aronov, Boris","last_name":"Aronov","first_name":"Boris"},{"full_name":"Chazelle, Bernard","last_name":"Chazelle","first_name":"Bernard"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"},{"first_name":"Rephael","last_name":"Wenger","full_name":"Wenger, Rephael"}],"article_processing_charge":"No","date_created":"2018-12-11T12:06:43Z","publication_status":"published","intvolume":"         6","title":"Points and triangles in the plane and halving planes in space","quality_controlled":"1","page":"435 - 442","publisher":"Springer","article_type":"original","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,” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1. Springer, pp. 435–442, 1991.","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.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1991. <a href=\"https://doi.org/10.1007/BF02574700\">https://doi.org/10.1007/BF02574700</a>.","apa":"Aronov, B., Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Wenger, R. (1991). Points and triangles in the plane and halving planes in space. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574700\">https://doi.org/10.1007/BF02574700</a>","ama":"Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. Points and triangles in the plane and halving planes in space. <i>Discrete &#38; Computational Geometry</i>. 1991;6(1):435-442. doi:<a href=\"https://doi.org/10.1007/BF02574700\">10.1007/BF02574700</a>","ista":"Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. 1991. Points and triangles in the plane and halving planes in space. Discrete &#38; Computational Geometry. 6(1), 435–442.","short":"B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, R. Wenger, Discrete &#38; Computational Geometry 6 (1991) 435–442.","mla":"Aronov, Boris, et al. “Points and Triangles in the Plane and Halving Planes in Space.” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1, Springer, 1991, pp. 435–42, doi:<a href=\"https://doi.org/10.1007/BF02574700\">10.1007/BF02574700</a>."},"year":"1991","date_updated":"2022-02-24T15:39:25Z","day":"01","doi":"10.1007/BF02574700","abstract":[{"lang":"eng","text":"We prove that for any set S of n points in the plane and n3-α triangles spanned by the points in S there exists a point (not necessarily in S) contained in at least n3-3α/(c log5 n) of the triangles. This implies that any set of n points in three-dimensional space defines at most {Mathematical expression} halving planes."}],"acknowledgement":"Work on this paper by Boris Aronov and Rephael Wenger has been supported by DIMACS under NSF Grant STC-88-09648. Work on this paper by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-87-14565. Micha Sharir has been supported by ONR Grant N00014-87-K-0129, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Israeli National Council for Research and Development, and the Fund for Basic Research administered by the Israeli\r\nAcademy of Sciences","volume":6,"extern":"1"},{"language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","month":"03","oa_version":"None","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187785"}],"type":"journal_article","date_published":"1990-03-01T00:00:00Z","publist_id":"2054","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"quality_controlled":"1","page":"197 - 216","article_type":"original","publisher":"Springer","issue":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"}],"scopus_import":"1","_id":"4066","intvolume":"         5","title":"The complexity of many cells in arrangements of planes and related problems","date_created":"2018-12-11T12:06:44Z","article_processing_charge":"No","publication_status":"published","extern":"1","acknowledgement":"Supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. I-6-44862 and by NSF Grant CCR-87t4565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-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. An abstract of this\r\npaper has appeared in the Proceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147","volume":5,"year":"1990","citation":{"mla":"Edelsbrunner, Herbert, et al. “The Complexity of Many Cells in Arrangements of Planes and Related Problems.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 197–216, doi:<a href=\"https://doi.org/10.1007/BF02187785\">10.1007/BF02187785</a>.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 5 (1990) 197–216.","ista":"Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity of many cells in arrangements of planes and related problems. Discrete &#38; Computational Geometry. 5(1), 197–216.","ama":"Edelsbrunner H, Guibas L, Sharir M. The complexity of many cells in arrangements of planes and related problems. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):197-216. doi:<a href=\"https://doi.org/10.1007/BF02187785\">10.1007/BF02187785</a>","apa":"Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1990). The complexity of many cells in arrangements of planes and related problems. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187785\">https://doi.org/10.1007/BF02187785</a>","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity of Many Cells in Arrangements of Planes and Related Problems.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187785\">https://doi.org/10.1007/BF02187785</a>.","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity of many cells in arrangements of planes and related problems,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 197–216, 1990."},"date_updated":"2022-02-22T11:02:41Z","abstract":[{"text":"We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m 2/3 n logn +n 2); we can calculatem such cells specified by a point in each, in worst-case timeO(m 2/3 n log3 n+n 2 logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m 2/3 n logn+n 2), but this number is onlyO(m 3/5– n 4/5+2 +m+n logm), for any&gt;0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m 3/4– n 3/4+3 +m) log2 n+n logn logm) for any&gt;0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m 3/4– n 3/4+3 +m] log2 n+n logn logm) for any&gt;0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d&gt;3, isO(m 2/3 n d/3 logn+n d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.","lang":"eng"}],"day":"01","doi":"10.1007/BF02187785"},{"oa_version":"None","month":"01","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publist_id":"2057","type":"journal_article","date_published":"1990-01-01T00:00:00Z","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187778"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","date_created":"2018-12-11T12:06:45Z","article_processing_charge":"No","publication_status":"published","intvolume":"         5","title":"The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2","_id":"4068","issue":"1","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"}],"publisher":"Springer","article_type":"original","quality_controlled":"1","page":"35 - 42","day":"01","doi":"10.1007/BF02187778","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\r\n(i1i2in−1in)(inin−1i2i1) \r\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","citation":{"chicago":"Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187778\">https://doi.org/10.1007/BF02187778</a>.","ieee":"H. Edelsbrunner and M. Sharir, “The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 35–42, 1990.","apa":"Edelsbrunner, H., &#38; Sharir, M. (1990). The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187778\">https://doi.org/10.1007/BF02187778</a>","ama":"Edelsbrunner H, Sharir M. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):35-42. doi:<a href=\"https://doi.org/10.1007/BF02187778\">10.1007/BF02187778</a>","ista":"Edelsbrunner H, Sharir M. 1990. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. Discrete &#38; Computational Geometry. 5(1), 35–42.","short":"H. Edelsbrunner, M. Sharir, Discrete &#38; Computational Geometry 5 (1990) 35–42.","mla":"Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 35–42, doi:<a href=\"https://doi.org/10.1007/BF02187778\">10.1007/BF02187778</a>."},"date_updated":"2022-02-22T14:50:34Z","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.","volume":5,"extern":"1"},{"language":[{"iso":"eng"}],"month":"01","oa_version":"None","publication":"Discrete & Computational Geometry","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187784"}],"publist_id":"2053","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"type":"journal_article","date_published":"1990-01-01T00:00:00Z","article_type":"original","publisher":"Springer","quality_controlled":"1","page":"161 - 196","intvolume":"         5","title":"The complexity and construction of many faces in arrangements of lines and of segments","date_created":"2018-12-11T12:06:46Z","article_processing_charge":"No","publication_status":"published","issue":"1","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"}],"scopus_import":"1","_id":"4072","extern":"1","volume":5,"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.","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&gt;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&gt;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"}],"day":"01","doi":"10.1007/BF02187784","year":"1990","citation":{"apa":"Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1990). The complexity and construction of many faces in arrangements of lines and of segments. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187784\">https://doi.org/10.1007/BF02187784</a>","ama":"Edelsbrunner H, Guibas L, Sharir M. The complexity and construction of many faces in arrangements of lines and of segments. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):161-196. doi:<a href=\"https://doi.org/10.1007/BF02187784\">10.1007/BF02187784</a>","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction of many faces in arrangements of lines and of segments,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 161–196, 1990.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187784\">https://doi.org/10.1007/BF02187784</a>.","mla":"Edelsbrunner, Herbert, et al. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 161–96, doi:<a href=\"https://doi.org/10.1007/BF02187784\">10.1007/BF02187784</a>.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 5 (1990) 161–196.","ista":"Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity and construction of many faces in arrangements of lines and of segments. Discrete &#38; Computational Geometry. 5(1), 161–196."},"date_updated":"2022-02-22T09:27:30Z"},{"extern":"1","acknowledgement":"The research of the second author was supported by the National Science Foundation under Grant CCR-8714565. Work by the fourth author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-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 29th IEEE Symposium on Foundations of Computer Science, 1988.","volume":5,"citation":{"short":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete &#38; Computational Geometry 5 (1990) 99–160.","mla":"Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 99–160, doi:<a href=\"https://doi.org/10.1007/BF02187783\">10.1007/BF02187783</a>.","ista":"Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. 1990. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete &#38; Computational Geometry. 5(1), 99–160.","apa":"Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Welzl, E. (1990). Combinatorial complexity bounds for arrangements of curves and spheres. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187783\">https://doi.org/10.1007/BF02187783</a>","ama":"Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity bounds for arrangements of curves and spheres. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):99-160. doi:<a href=\"https://doi.org/10.1007/BF02187783\">10.1007/BF02187783</a>","chicago":"Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187783\">https://doi.org/10.1007/BF02187783</a>.","ieee":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial complexity bounds for arrangements of curves and spheres,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 99–160, 1990."},"year":"1990","date_updated":"2022-02-17T15:41:04Z","abstract":[{"lang":"eng","text":"We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n), and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m 4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given."}],"day":"01","doi":"10.1007/BF02187783","quality_controlled":"1","page":"99 - 160","article_type":"original","publisher":"Springer","issue":"1","author":[{"full_name":"Clarkson, Kenneth","last_name":"Clarkson","first_name":"Kenneth"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"_id":"4074","intvolume":"         5","title":"Combinatorial complexity bounds for arrangements of curves and spheres","article_processing_charge":"No","date_created":"2018-12-11T12:06:47Z","publication_status":"published","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187783"}],"type":"journal_article","date_published":"1990-03-01T00:00:00Z","publist_id":"2048","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","month":"03","oa_version":"None"},{"article_type":"original","publisher":"Springer","quality_controlled":"1","page":"311 - 336","intvolume":"         4","title":"The upper envelope of piecewise linear functions: Algorithms and applications","date_created":"2018-12-11T12:06:50Z","article_processing_charge":"No","publication_status":"published","issue":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"}],"_id":"4081","extern":"1","volume":4,"acknowledgement":"Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862. Work by the third author has been supported by the Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a research grant from NCRD, the Israeli National Council for Research and Development.","abstract":[{"lang":"eng","text":"This paper studies applications of envelopes of piecewise linear functions to problems in computational geometry. Among these applications we find problems involving hidden line/surface elimination, motion planning, transversals of polytopes, and a new type of Voronoi diagram for clusters of points. All results are either combinatorial or computational in nature. They are based on the combinatorial analysis in two companion papers [PS] and [E2] and a divide-and-conquer algorithm for computing envelopes described in this paper."}],"day":"01","doi":"10.1007/BF02187733","year":"1989","citation":{"ista":"Edelsbrunner H, Guibas L, Sharir M. 1989. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete &#38; Computational Geometry. 4(1), 311–336.","mla":"Edelsbrunner, Herbert, et al. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 311–36, doi:<a href=\"https://doi.org/10.1007/BF02187733\">10.1007/BF02187733</a>.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 4 (1989) 311–336.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187733\">https://doi.org/10.1007/BF02187733</a>.","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The upper envelope of piecewise linear functions: Algorithms and applications,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 311–336, 1989.","ama":"Edelsbrunner H, Guibas L, Sharir M. The upper envelope of piecewise linear functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):311-336. doi:<a href=\"https://doi.org/10.1007/BF02187733\">10.1007/BF02187733</a>","apa":"Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1989). The upper envelope of piecewise linear functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187733\">https://doi.org/10.1007/BF02187733</a>"},"date_updated":"2022-02-10T15:53:48Z","language":[{"iso":"eng"}],"month":"12","oa_version":"Published Version","publication":"Discrete & Computational Geometry","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02187733"}],"publist_id":"2038","oa":1,"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"type":"journal_article","date_published":"1989-12-01T00:00:00Z"},{"date_updated":"2022-02-10T11:08:12Z","year":"1989","citation":{"apa":"Edelsbrunner, H. (1989). The upper envelope of piecewise linear functions: Tight bounds on the number of faces . <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187734\">https://doi.org/10.1007/BF02187734</a>","ama":"Edelsbrunner H. The upper envelope of piecewise linear functions: Tight bounds on the number of faces . <i>Discrete &#38; Computational Geometry</i>. 1989;4(4):337-343. doi:<a href=\"https://doi.org/10.1007/BF02187734\">10.1007/BF02187734</a>","ieee":"H. Edelsbrunner, “The upper envelope of piecewise linear functions: Tight bounds on the number of faces ,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 4. Springer, pp. 337–343, 1989.","chicago":"Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces .” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187734\">https://doi.org/10.1007/BF02187734</a>.","short":"H. Edelsbrunner, Discrete &#38; Computational Geometry 4 (1989) 337–343.","mla":"Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces .” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 4, Springer, 1989, pp. 337–43, doi:<a href=\"https://doi.org/10.1007/BF02187734\">10.1007/BF02187734</a>.","ista":"Edelsbrunner H. 1989. The upper envelope of piecewise linear functions: Tight bounds on the number of faces . Discrete &#38; Computational Geometry. 4(4), 337–343."},"doi":"10.1007/BF02187734","day":"01","abstract":[{"text":"This note proves that the maximum number of faces (of any dimension) of the upper envelope of a set ofn possibly intersectingd-simplices ind+1 dimensions is (n d (n)). This is an extension of a result of Pach and Sharir [PS] who prove the same bound for the number ofd-dimensional faces of the upper envelope.","lang":"eng"}],"volume":4,"acknowledgement":"This work was supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under Grant CCR-8714565. Research on the presented result was partially carried out while the author worked for the IBM T. J. Watson Research Center at Yorktown Height, New York, USA. \r\n","extern":"1","_id":"4086","scopus_import":"1","author":[{"last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"issue":"4","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:06:51Z","title":"The upper envelope of piecewise linear functions: Tight bounds on the number of faces ","intvolume":"         4","page":"337 - 343","quality_controlled":"1","publisher":"Springer","article_type":"original","date_published":"1989-11-01T00:00:00Z","type":"journal_article","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"oa":1,"publist_id":"2034","main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02187734"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication":"Discrete & Computational Geometry","oa_version":"Published Version","month":"11","language":[{"iso":"eng"}]},{"publisher":"Springer","article_type":"original","quality_controlled":"1","page":"433 - 466","article_processing_charge":"No","date_created":"2018-12-11T12:06:52Z","publication_status":"published","intvolume":"         4","title":"Implicitly representing arrangements of lines or segments","scopus_import":"1","_id":"4088","issue":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"},{"full_name":"Hershberger, John","first_name":"John","last_name":"Hershberger"},{"last_name":"Seidel","first_name":"Raimund","full_name":"Seidel, Raimund"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"},{"full_name":"Snoeyink, Jack","first_name":"Jack","last_name":"Snoeyink"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"volume":4,"acknowledgement":"The first author is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565. Work on this paper by the fifth author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-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. The sixth author was supported in part by a National Science Foundation Graduate Fellowship. This work was begun while the non-DEC authors were visiting at the DEC Systems Research Center.","extern":"1","day":"01","doi":"10.1007/BF02187742","abstract":[{"lang":"eng","text":"Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, (2) given a simple polygonal path , form a data structure from which we can find the convex hull of any subpath of quickly, and (3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal."}],"year":"1989","citation":{"ieee":"H. Edelsbrunner <i>et al.</i>, “Implicitly representing arrangements of lines or segments,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 433–466, 1989.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, Raimund Seidel, Micha Sharir, Jack Snoeyink, and Emo Welzl. “Implicitly Representing Arrangements of Lines or Segments.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187742\">https://doi.org/10.1007/BF02187742</a>.","ama":"Edelsbrunner H, Guibas L, Hershberger J, et al. Implicitly representing arrangements of lines or segments. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):433-466. doi:<a href=\"https://doi.org/10.1007/BF02187742\">10.1007/BF02187742</a>","apa":"Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., Sharir, M., Snoeyink, J., &#38; Welzl, E. (1989). Implicitly representing arrangements of lines or segments. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187742\">https://doi.org/10.1007/BF02187742</a>","ista":"Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M, Snoeyink J, Welzl E. 1989. Implicitly representing arrangements of lines or segments. Discrete &#38; Computational Geometry. 4(1), 433–466.","mla":"Edelsbrunner, Herbert, et al. “Implicitly Representing Arrangements of Lines or Segments.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 433–66, doi:<a href=\"https://doi.org/10.1007/BF02187742\">10.1007/BF02187742</a>.","short":"H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, E. Welzl, Discrete &#38; Computational Geometry 4 (1989) 433–466."},"date_updated":"2022-02-10T15:03:48Z","language":[{"iso":"eng"}],"oa_version":"Published Version","month":"12","publication":"Discrete & Computational Geometry","main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02187742"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publist_id":"2036","oa":1,"type":"journal_article","date_published":"1989-12-01T00:00:00Z"},{"acknowledgement":"The first author is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565. Work on this paper by the fourth and seventh authors has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. The seventh author in addition wishes to acknowledge support by a research grant from the NCRD—the Israeli National Council for Research and Development. The fifth author would like to acknowledge support in part by NSF grant DMS-8501947. Finally, the eighth author was supported in part by a National Science Foundation Graduate Fellowship.","volume":4,"extern":"1","doi":"10.1007/BF02187745","day":"01","abstract":[{"lang":"eng","text":"Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only (n(n)), where(n) is the extremely slowly growing functional inverse of Ackermann's function."}],"date_updated":"2022-02-10T15:40:04Z","citation":{"ama":"Edelsbrunner H, Guibas L, Hershberger J, et al. On arrangements of Jordan arcs with three intersections per pair. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):523-539. doi:<a href=\"https://doi.org/10.1007/BF02187745\">10.1007/BF02187745</a>","apa":"Edelsbrunner, H., Guibas, L., Hershberger, J., Pach, J., Pollack, R., Seidel, R., … Snoeyink, J. (1989). On arrangements of Jordan arcs with three intersections per pair. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187745\">https://doi.org/10.1007/BF02187745</a>","ieee":"H. Edelsbrunner <i>et al.</i>, “On arrangements of Jordan arcs with three intersections per pair,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 523–539, 1989.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir, and Jack Snoeyink. “On Arrangements of Jordan Arcs with Three Intersections per Pair.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187745\">https://doi.org/10.1007/BF02187745</a>.","mla":"Edelsbrunner, Herbert, et al. “On Arrangements of Jordan Arcs with Three Intersections per Pair.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 523–39, doi:<a href=\"https://doi.org/10.1007/BF02187745\">10.1007/BF02187745</a>.","short":"H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink, Discrete &#38; Computational Geometry 4 (1989) 523–539.","ista":"Edelsbrunner H, Guibas L, Hershberger J, Pach J, Pollack R, Seidel R, Sharir M, Snoeyink J. 1989. On arrangements of Jordan arcs with three intersections per pair. Discrete &#38; Computational Geometry. 4(1), 523–539."},"year":"1989","publisher":"Springer","article_type":"original","page":"523 - 539","quality_controlled":"1","publication_status":"published","date_created":"2018-12-11T12:06:52Z","article_processing_charge":"No","title":"On arrangements of Jordan arcs with three intersections per pair","intvolume":"         4","_id":"4089","scopus_import":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"},{"first_name":"John","last_name":"Hershberger","full_name":"Hershberger, John"},{"first_name":"János","last_name":"Pach","full_name":"Pach, János"},{"full_name":"Pollack, Richard","first_name":"Richard","last_name":"Pollack"},{"first_name":"Raimund","last_name":"Seidel","full_name":"Seidel, Raimund"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"},{"full_name":"Snoeyink, Jack","last_name":"Snoeyink","first_name":"Jack"}],"issue":"1","main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02187745"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"oa":1,"publist_id":"2037","date_published":"1989-12-01T00:00:00Z","type":"journal_article","language":[{"iso":"eng"}],"oa_version":"Published Version","month":"12","publication":"Discrete & Computational Geometry"},{"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187720"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","type":"journal_article","date_published":"1989-03-01T00:00:00Z","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publist_id":"2032","language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","oa_version":"None","month":"03","acknowledgement":"Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant No. MCS83-03925. Herbert Edelsbrunner is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862. We wish to thank J. Pach and E. Szemeredi for valuable discussions on several\r\nof the problems studied in this paper.","volume":4,"extern":"1","year":"1989","citation":{"ista":"Chazelle B, Edelsbrunner H, Guibas L. 1989. The complexity of cutting complexes. Discrete &#38; Computational Geometry. 4(1), 139–181.","mla":"Chazelle, Bernard, et al. “The Complexity of Cutting Complexes.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 139–81, doi:<a href=\"https://doi.org/10.1007/BF02187720\">10.1007/BF02187720</a>.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, Discrete &#38; Computational Geometry 4 (1989) 139–181.","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, and Leonidas Guibas. “The Complexity of Cutting Complexes.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187720\">https://doi.org/10.1007/BF02187720</a>.","ieee":"B. Chazelle, H. Edelsbrunner, and L. Guibas, “The complexity of cutting complexes,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 139–181, 1989.","ama":"Chazelle B, Edelsbrunner H, Guibas L. The complexity of cutting complexes. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):139-181. doi:<a href=\"https://doi.org/10.1007/BF02187720\">10.1007/BF02187720</a>","apa":"Chazelle, B., Edelsbrunner, H., &#38; Guibas, L. (1989). The complexity of cutting complexes. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187720\">https://doi.org/10.1007/BF02187720</a>"},"date_updated":"2022-02-10T10:25:57Z","day":"01","doi":"10.1007/BF02187720","abstract":[{"lang":"eng","text":"This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross-section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed."}],"quality_controlled":"1","page":"139 - 181","publisher":"Springer","_id":"4093","issue":"1","author":[{"last_name":"Chazelle","first_name":"Bernard","full_name":"Chazelle, Bernard"},{"orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"}],"article_processing_charge":"No","date_created":"2018-12-11T12:06:54Z","publication_status":"published","intvolume":"         4","title":"The complexity of cutting complexes"},{"type":"journal_article","date_published":"1987-01-01T00:00:00Z","publist_id":"2022","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","publication":"Discrete & Computational Geometry","month":"01","oa_version":"None","language":[{"iso":"eng"}],"year":"1987","citation":{"mla":"Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures for Two Types of Range Search.” <i>Discrete &#38; Computational Geometry</i>, vol. 2, no. 1, Springer, 1987, pp. 113–26, doi:<a href=\"https://doi.org/10.1007/BF02187875\">10.1007/BF02187875</a>.","short":"B. Chazelle, H. Edelsbrunner, Discrete &#38; Computational Geometry 2 (1987) 113–126.","ista":"Chazelle B, Edelsbrunner H. 1987. Linear space data structures for two types of range search. Discrete &#38; Computational Geometry. 2(1), 113–126.","apa":"Chazelle, B., &#38; Edelsbrunner, H. (1987). Linear space data structures for two types of range search. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187875\">https://doi.org/10.1007/BF02187875</a>","ama":"Chazelle B, Edelsbrunner H. Linear space data structures for two types of range search. <i>Discrete &#38; Computational Geometry</i>. 1987;2(1):113-126. doi:<a href=\"https://doi.org/10.1007/BF02187875\">10.1007/BF02187875</a>","chicago":"Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures for Two Types of Range Search.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1987. <a href=\"https://doi.org/10.1007/BF02187875\">https://doi.org/10.1007/BF02187875</a>.","ieee":"B. Chazelle and H. Edelsbrunner, “Linear space data structures for two types of range search,” <i>Discrete &#38; Computational Geometry</i>, vol. 2, no. 1. Springer, pp. 113–126, 1987."},"date_updated":"2022-02-03T11:07:26Z","abstract":[{"text":"This paper investigates the existence of linear space data structures for range searching. We examine thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently. We also look atdomination searching in three dimensions. In this problem,S is a set ofn points inE 3 and the question is to retrieve all points ofS that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and nearly optimal in the second.\r\n","lang":"eng"}],"day":"01","doi":"10.1007/BF02187875","extern":"1","acknowledgement":"This research was conducted while the first author was with Brown University and the second author was with the Technical University of Graz, Austria. The first author was supported in part by NSF Grant MCS 83-03925.","volume":2,"issue":"1","author":[{"full_name":"Chazelle, Bernard","first_name":"Bernard","last_name":"Chazelle"},{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":"1","_id":"4100","intvolume":"         2","title":"Linear space data structures for two types of range search","date_created":"2018-12-11T12:06:56Z","article_processing_charge":"No","publication_status":"published","quality_controlled":"1","page":"113 - 126","article_type":"original","publisher":"Springer"},{"volume":1,"acknowledgement":"We would like to thank John Gilbert for his careful reading of the manuscript and his many suggestions for improvement. We also want to thank Bennett Battaile, Gianfranco Bilardi, Joseph O'Rourke, and Chee Yap for their comments. ","extern":"1","date_updated":"2022-02-01T08:53:39Z","year":"1986","citation":{"apa":"Edelsbrunner, H., &#38; Seidel, R. (1986). Voronoi diagrams and arrangements. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187681\">https://doi.org/10.1007/BF02187681</a>","ama":"Edelsbrunner H, Seidel R. Voronoi diagrams and arrangements. <i>Discrete &#38; Computational Geometry</i>. 1986;1(1):25-44. doi:<a href=\"https://doi.org/10.1007/BF02187681\">10.1007/BF02187681</a>","ieee":"H. Edelsbrunner and R. Seidel, “Voronoi diagrams and arrangements,” <i>Discrete &#38; Computational Geometry</i>, vol. 1, no. 1. Springer, pp. 25–44, 1986.","chicago":"Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1986. <a href=\"https://doi.org/10.1007/BF02187681\">https://doi.org/10.1007/BF02187681</a>.","mla":"Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.” <i>Discrete &#38; Computational Geometry</i>, vol. 1, no. 1, Springer, 1986, pp. 25–44, doi:<a href=\"https://doi.org/10.1007/BF02187681\">10.1007/BF02187681</a>.","short":"H. Edelsbrunner, R. Seidel, Discrete &#38; Computational Geometry 1 (1986) 25–44.","ista":"Edelsbrunner H, Seidel R. 1986. Voronoi diagrams and arrangements. Discrete &#38; Computational Geometry. 1(1), 25–44."},"doi":"10.1007/BF02187681","day":"01","abstract":[{"lang":"eng","text":"We propose a uniform and general framework for defining and dealing with Voronoi diagrams. In this framework a Voronoi diagram is a partition of a domainD induced by a finite number of real valued functions onD. Valuable insight can be gained when one considers how these real valued functions partitionD ×R. With this view it turns out that the standard Euclidean Voronoi diagram of point sets inR d along with its order-k generalizations are intimately related to certain arrangements of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms. We also discuss how the formalism of arrangements can be used to solve certain intersection and union problems."}],"page":"25 - 44","quality_controlled":"1","publisher":"Springer","article_type":"original","_id":"4108","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"full_name":"Seidel, Raimund","last_name":"Seidel","first_name":"Raimund"}],"issue":"1","publication_status":"published","date_created":"2018-12-11T12:06:59Z","article_processing_charge":"No","title":"Voronoi diagrams and arrangements","intvolume":"         1","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","date_published":"1986-01-01T00:00:00Z","type":"journal_article","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publist_id":"2012","language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","oa_version":"None","month":"01"}]