[{"extern":"1","oa_version":"None","article_type":"original","acknowledgement":"We thank Emmerich Welzl for discussions on Theorem 2.7. We also thank Friedrich Huber for implementing the \r\nconstruction of arrangements in arbitrary dimensions, and Gerd Stoeckl for implementing the algorithms presented in §§\r\n4.1 and 4.3. The third author wishes to thank Jack Edmonds for the many enlightening discussions.\r\n","status":"public","publication":"SIAM Journal on Computing","publisher":"SIAM","citation":{"short":"H. Edelsbrunner, J. O’Rourke, R. Seidel, SIAM Journal on Computing 15 (1986) 341–363.","ieee":"H. Edelsbrunner, J. O’Rourke, and R. Seidel, “Constructing arrangements of lines and hyperplanes with applications,” <i>SIAM Journal on Computing</i>, vol. 15, no. 2. SIAM, pp. 341–363, 1986.","ama":"Edelsbrunner H, O’Rourke J, Seidel R. Constructing arrangements of lines and hyperplanes with applications. <i>SIAM Journal on Computing</i>. 1986;15(2):341-363. doi:<a href=\"https://doi.org/10.1137/0215024\">10.1137/0215024</a>","apa":"Edelsbrunner, H., O’Rourke, J., &#38; Seidel, R. (1986). Constructing arrangements of lines and hyperplanes with applications. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/0215024\">https://doi.org/10.1137/0215024</a>","ista":"Edelsbrunner H, O’Rourke J, Seidel R. 1986. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing. 15(2), 341–363.","mla":"Edelsbrunner, Herbert, et al. “Constructing Arrangements of Lines and Hyperplanes with Applications.” <i>SIAM Journal on Computing</i>, vol. 15, no. 2, SIAM, 1986, pp. 341–63, doi:<a href=\"https://doi.org/10.1137/0215024\">10.1137/0215024</a>.","chicago":"Edelsbrunner, Herbert, Joseph O’Rourke, and Raimund Seidel. “Constructing Arrangements of Lines and Hyperplanes with Applications.” <i>SIAM Journal on Computing</i>. SIAM, 1986. <a href=\"https://doi.org/10.1137/0215024\">https://doi.org/10.1137/0215024</a>."},"scopus_import":"1","month":"01","author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"first_name":"Joseph","last_name":"O'Rourke","full_name":"O'Rourke, Joseph"},{"full_name":"Seidel, Raimund","last_name":"Seidel","first_name":"Raimund"}],"title":"Constructing arrangements of lines and hyperplanes with applications","article_processing_charge":"No","issue":"2","publist_id":"2017","type":"journal_article","date_updated":"2022-02-01T11:03:07Z","_id":"4105","date_published":"1986-01-01T00:00:00Z","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","quality_controlled":"1","volume":15,"publication_status":"published","doi":"10.1137/0215024","intvolume":"        15","day":"01","abstract":[{"lang":"eng","text":"A finite set of lines partitions the Euclidean plane into a cell complex. Similarly, a finite set of $(d - 1)$-dimensional hyperplanes partitions $d$-dimensional Euclidean space. An algorithm is presented that constructs a representation for the cell complex defined by $n$ hyperplanes in optimal $O(n^d )$ time in $d$ dimensions. It relies on a combinatorial result that is of interest in its own right. The algorithm is shown to lead to new methods for computing $\\lambda $-matrices, constructing all higher-order Voronoi diagrams, halfspatial range estimation, degeneracy testing, and finding minimum measure simplices. In all five applications, the new algorithms are asymptotically faster than previous results, and in several cases are the only known methods that generalize to arbitrary dimensions. The algorithm also implies an upper bound of $2^{cn^d } $, $c$ a positive constant, for the number of combinatorially distinct arrangements of $n$ hyperplanes in $E^d $.\r\n© 1986 Society for Industrial and Applied Mathematics"}],"language":[{"iso":"eng"}],"date_created":"2018-12-11T12:06:58Z","page":"341 - 363","year":"1986"},{"date_created":"2018-12-11T12:07:00Z","page":"271 - 284","year":"1986","day":"01","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"For H a set of lines in the Euclidean plane, $A(H)$ denotes the induced dissection, called the arrangement of H. We define the notion of a belt in $A(H)$, which is bounded by a subset of the edges in $A(H)$, and describe two algorithms for constructing belts. All this is motivated by applications to a host of seemingly unrelated problems including a type of range search and finding the minimum area triangle with the vertices taken from some finite set of points."}],"intvolume":"        15","publication_status":"published","doi":"10.1137/0215019","volume":15,"publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","date_published":"1986-01-01T00:00:00Z","quality_controlled":"1","_id":"4110","date_updated":"2022-02-01T09:34:20Z","type":"journal_article","publist_id":"2014","issue":"1","title":"Constructing belts in two-dimensional arrangements with applications","article_processing_charge":"No","month":"01","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"first_name":"Emo","full_name":"Welzl, Emo","last_name":"Welzl"}],"citation":{"apa":"Edelsbrunner, H., &#38; Welzl, E. (1986). Constructing belts in two-dimensional arrangements with applications. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/0215019\">https://doi.org/10.1137/0215019</a>","ama":"Edelsbrunner H, Welzl E. Constructing belts in two-dimensional arrangements with applications. <i>SIAM Journal on Computing</i>. 1986;15(1):271-284. doi:<a href=\"https://doi.org/10.1137/0215019\">10.1137/0215019</a>","ieee":"H. Edelsbrunner and E. Welzl, “Constructing belts in two-dimensional arrangements with applications,” <i>SIAM Journal on Computing</i>, vol. 15, no. 1. SIAM, pp. 271–284, 1986.","short":"H. Edelsbrunner, E. Welzl, SIAM Journal on Computing 15 (1986) 271–284.","mla":"Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional Arrangements with Applications.” <i>SIAM Journal on Computing</i>, vol. 15, no. 1, SIAM, 1986, pp. 271–84, doi:<a href=\"https://doi.org/10.1137/0215019\">10.1137/0215019</a>.","ista":"Edelsbrunner H, Welzl E. 1986. Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing. 15(1), 271–284.","chicago":"Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional Arrangements with Applications.” <i>SIAM Journal on Computing</i>. SIAM, 1986. <a href=\"https://doi.org/10.1137/0215019\">https://doi.org/10.1137/0215019</a>."},"scopus_import":"1","publisher":"SIAM","publication":"SIAM Journal on Computing","status":"public","article_type":"original","oa_version":"None","extern":"1"}]