[{"scopus_import":"1","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"date_published":"1989-04-01T00:00:00Z","page":"371 - 384","doi":"10.1137/0218025","language":[{"iso":"eng"}],"oa_version":"Published Version","date_updated":"2022-02-11T07:55:48Z","type":"journal_article","day":"01","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","article_processing_charge":"No","month":"04","date_created":"2018-12-11T12:06:50Z","status":"public","intvolume":"        18","publist_id":"2040","article_type":"original","publisher":"SIAM","issue":"2","volume":18,"abstract":[{"lang":"eng","text":"It is shown that, given a set S of n points in $R^3 $, one can always find three planes that form an eight-partition of S, that is, a partition where at most ${n / 8}$ points of S lie in each of the eight open regions. This theorem is used to define a data structure, called an octant tree, for representing any point set in $R^3 $. An octant tree for n points occupies $O(n)$ space and can be constructed in polynomial time. With this data structure and its refinements, efficient solutions to various range query problems in two and three dimensions can be obtained, including (1) half-space queries: find all points of S that lie to one side of any given plane; (2) polyhedron queries: find all points that lie inside (outside) any given polyhedron; and (3) circle queries in $R^2 $: for a planar set S, find all points that lie inside (outside) any given circle. The retrieval time for all these queries is $T(n) = O(n^\\alpha + m)$, where $\\alpha = 0.8988$ (or 0.8471 in case (3)), and m is the size of the output. This performance is the best currently known for linear-space data structures that can be deterministically constructed in polynomial time."}],"publication_status":"published","publication":"SIAM Journal on Computing","title":"Partitioning space for range queries","_id":"4083","oa":1,"year":"1989","main_file_link":[{"open_access":"1","url":"https://epubs.siam.org/doi/10.1137/0218025"}],"citation":{"apa":"Yao, F., Dobkin, D., Edelsbrunner, H., &#38; Paterson, M. (1989). Partitioning space for range queries. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/0218025\">https://doi.org/10.1137/0218025</a>","mla":"Yao, F., et al. “Partitioning Space for Range Queries.” <i>SIAM Journal on Computing</i>, vol. 18, no. 2, SIAM, 1989, pp. 371–84, doi:<a href=\"https://doi.org/10.1137/0218025\">10.1137/0218025</a>.","ista":"Yao F, Dobkin D, Edelsbrunner H, Paterson M. 1989. Partitioning space for range queries. SIAM Journal on Computing. 18(2), 371–384.","short":"F. Yao, D. Dobkin, H. Edelsbrunner, M. Paterson, SIAM Journal on Computing 18 (1989) 371–384.","chicago":"Yao, F., David Dobkin, Herbert Edelsbrunner, and Michael Paterson. “Partitioning Space for Range Queries.” <i>SIAM Journal on Computing</i>. SIAM, 1989. <a href=\"https://doi.org/10.1137/0218025\">https://doi.org/10.1137/0218025</a>.","ieee":"F. Yao, D. Dobkin, H. Edelsbrunner, and M. Paterson, “Partitioning space for range queries,” <i>SIAM Journal on Computing</i>, vol. 18, no. 2. SIAM, pp. 371–384, 1989.","ama":"Yao F, Dobkin D, Edelsbrunner H, Paterson M. Partitioning space for range queries. <i>SIAM Journal on Computing</i>. 1989;18(2):371-384. doi:<a href=\"https://doi.org/10.1137/0218025\">10.1137/0218025</a>"},"quality_controlled":"1","extern":"1","author":[{"first_name":"F.","last_name":"Yao","full_name":"Yao, F."},{"full_name":"Dobkin, David","last_name":"Dobkin","first_name":"David"},{"last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Paterson, Michael","first_name":"Michael","last_name":"Paterson"}]},{"date_published":"1988-01-01T00:00:00Z","page":"870 - 882","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"scopus_import":"1","type":"journal_article","date_updated":"2022-02-08T11:14:23Z","oa_version":"None","day":"01","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","article_processing_charge":"No","acknowledgement":"The research of this author was supported by the Amoco Foundation Facility for the Development of Computer Science 1-6-44862.","doi":"10.1137/0217054 ","language":[{"iso":"eng"}],"article_type":"original","publisher":"SIAM","volume":17,"issue":"5","date_created":"2018-12-11T12:06:53Z","month":"01","status":"public","intvolume":"        17","publist_id":"2030","year":"1988","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0217054"}],"citation":{"mla":"Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” <i>SIAM Journal on Computing</i>, vol. 17, no. 5, SIAM, 1988, pp. 870–82, doi:<a href=\"https://doi.org/10.1137/0217054 \">10.1137/0217054 </a>.","apa":"Edelsbrunner, H., &#38; Skiena, S. (1988). Probing convex polygons with X-Rays. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/0217054 \">https://doi.org/10.1137/0217054 </a>","short":"H. Edelsbrunner, S. Skiena, SIAM Journal on Computing 17 (1988) 870–882.","chicago":"Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” <i>SIAM Journal on Computing</i>. SIAM, 1988. <a href=\"https://doi.org/10.1137/0217054 \">https://doi.org/10.1137/0217054 </a>.","ista":"Edelsbrunner H, Skiena S. 1988. Probing convex polygons with X-Rays. SIAM Journal on Computing. 17(5), 870–882.","ieee":"H. Edelsbrunner and S. Skiena, “Probing convex polygons with X-Rays,” <i>SIAM Journal on Computing</i>, vol. 17, no. 5. SIAM, pp. 870–882, 1988.","ama":"Edelsbrunner H, Skiena S. Probing convex polygons with X-Rays. <i>SIAM Journal on Computing</i>. 1988;17(5):870-882. doi:<a href=\"https://doi.org/10.1137/0217054 \">10.1137/0217054 </a>"},"quality_controlled":"1","extern":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert"},{"first_name":"Steven","last_name":"Skiena","full_name":"Skiena, Steven"}],"publication_status":"published","abstract":[{"text":"An X-ray probe through a polygon measures the length of intersection between a line and the polygon. This paper considers the properties of various classes of X-ray probes, and shows how they interact to give finite strategies for completely describing convex n-gons. It is shown that (3n/2)+6 probes are sufficient to verify a specified n-gon, while for determining convex polygons (3n-1)/2 X-ray probes are necesssary and 5n+O(1) sufficient, with 3n+O(1) sufficient given that a lower bound on the size of the smallest edge of P is known.","lang":"eng"}],"publication":"SIAM Journal on Computing","title":"Probing convex polygons with X-Rays","_id":"4091"},{"language":[{"iso":"eng"}],"doi":"10.1137/0215023","acknowledgement":"We would like to thank Andrei Broder, Dan Greene, Mary Claire van Leunen, Greg Nelson, Lyle Ramshaw, and F. Frances Yao, whose comments and suggestions have greatly improved the readability of this paper.","article_processing_charge":"No","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","day":"01","oa_version":"None","date_updated":"2022-02-01T10:05:55Z","type":"journal_article","scopus_import":"1","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"page":"317 - 340","date_published":"1986-01-01T00:00:00Z","_id":"4104","title":"Optimal point location in a monotone subdivision","publication":"SIAM Journal on Computing","abstract":[{"lang":"eng","text":"Point location, often known in graphics as “hit detection,” is one of the fundamental problems of computational geometry. In a point location query we want to identify which of a given collection of geometric objects contains a particular point. Let $\\mathcal{S}$ denote a subdivision of the Euclidean plane into monotone regions by a straight-line graph of $m$ edges. In this paper we exhibit a substantial refinement of the technique of Lee and Preparata [SIAM J. Comput., 6 (1977), pp. 594–606] for locating a point in $\\mathcal{S}$ based on separating chains. The new data structure, called a layered dag, can be built in $O(m)$ time, uses $O(m)$ storage, and makes possible point location in $O(\\log m)$ time. Unlike previous structures that attain these optimal bounds, the layered dag can be implemented in a simple and practical way, and is extensible to subdivisions with edges more general than straight-line segments.\r\n© 1986 Society for Industrial and Applied Mathematics"}],"publication_status":"published","extern":"1","quality_controlled":"1","author":[{"first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"full_name":"Stolfi, Jorge","first_name":"Jorge","last_name":"Stolfi"}],"citation":{"ama":"Edelsbrunner H, Guibas L, Stolfi J. Optimal point location in a monotone subdivision. <i>SIAM Journal on Computing</i>. 1986;15(2):317-340. doi:<a href=\"https://doi.org/10.1137/0215023\">10.1137/0215023</a>","ieee":"H. Edelsbrunner, L. Guibas, and J. Stolfi, “Optimal point location in a monotone subdivision,” <i>SIAM Journal on Computing</i>, vol. 15, no. 2. SIAM, pp. 317–340, 1986.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Jorge Stolfi. “Optimal Point Location in a Monotone Subdivision.” <i>SIAM Journal on Computing</i>. SIAM, 1986. <a href=\"https://doi.org/10.1137/0215023\">https://doi.org/10.1137/0215023</a>.","short":"H. Edelsbrunner, L. Guibas, J. Stolfi, SIAM Journal on Computing 15 (1986) 317–340.","ista":"Edelsbrunner H, Guibas L, Stolfi J. 1986. Optimal point location in a monotone subdivision. SIAM Journal on Computing. 15(2), 317–340.","apa":"Edelsbrunner, H., Guibas, L., &#38; Stolfi, J. (1986). Optimal point location in a monotone subdivision. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/0215023\">https://doi.org/10.1137/0215023</a>","mla":"Edelsbrunner, Herbert, et al. “Optimal Point Location in a Monotone Subdivision.” <i>SIAM Journal on Computing</i>, vol. 15, no. 2, SIAM, 1986, pp. 317–40, doi:<a href=\"https://doi.org/10.1137/0215023\">10.1137/0215023</a>."},"year":"1986","publist_id":"2016","intvolume":"        15","status":"public","month":"01","date_created":"2018-12-11T12:06:58Z","issue":"2","volume":15,"publisher":"SIAM","article_type":"original"},{"volume":15,"issue":"2","publisher":"SIAM","article_type":"original","publist_id":"2017","intvolume":"        15","status":"public","month":"01","date_created":"2018-12-11T12:06:58Z","quality_controlled":"1","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"O'Rourke, Joseph","first_name":"Joseph","last_name":"O'Rourke"},{"full_name":"Seidel, Raimund","first_name":"Raimund","last_name":"Seidel"}],"extern":"1","citation":{"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>","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>.","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>","short":"H. Edelsbrunner, J. O’Rourke, R. Seidel, SIAM Journal on Computing 15 (1986) 341–363.","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>.","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."},"year":"1986","_id":"4105","title":"Constructing arrangements of lines and hyperplanes with applications","publication":"SIAM Journal on Computing","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"}],"publication_status":"published","page":"341 - 363","date_published":"1986-01-01T00:00:00Z","scopus_import":"1","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","article_processing_charge":"No","day":"01","oa_version":"None","date_updated":"2022-02-01T11:03:07Z","type":"journal_article","language":[{"iso":"eng"}],"doi":"10.1137/0215024","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"},{"doi":"10.1137/0215019","language":[{"iso":"eng"}],"article_processing_charge":"No","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","day":"01","type":"journal_article","date_updated":"2022-02-01T09:34:20Z","oa_version":"None","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"scopus_import":"1","page":"271 - 284","date_published":"1986-01-01T00:00:00Z","_id":"4110","publication":"SIAM Journal on Computing","title":"Constructing belts in two-dimensional arrangements with applications","publication_status":"published","abstract":[{"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.","lang":"eng"}],"author":[{"first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"extern":"1","quality_controlled":"1","citation":{"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.","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>","ista":"Edelsbrunner H, Welzl E. 1986. Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing. 15(1), 271–284.","short":"H. Edelsbrunner, E. Welzl, SIAM Journal on Computing 15 (1986) 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>.","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>.","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>"},"year":"1986","publist_id":"2014","intvolume":"        15","status":"public","date_created":"2018-12-11T12:07:00Z","month":"01","volume":15,"issue":"1","publisher":"SIAM","article_type":"original"}]