--- _id: '4083' 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.' article_processing_charge: No article_type: original author: - first_name: F. full_name: Yao, F. last_name: Yao - first_name: David full_name: Dobkin, David last_name: Dobkin - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Michael full_name: Paterson, Michael last_name: Paterson citation: ama: Yao F, Dobkin D, Edelsbrunner H, Paterson M. Partitioning space for range queries. SIAM Journal on Computing. 1989;18(2):371-384. doi:10.1137/0218025 apa: Yao, F., Dobkin, D., Edelsbrunner, H., & Paterson, M. (1989). Partitioning space for range queries. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0218025 chicago: Yao, F., David Dobkin, Herbert Edelsbrunner, and Michael Paterson. “Partitioning Space for Range Queries.” SIAM Journal on Computing. SIAM, 1989. https://doi.org/10.1137/0218025. ieee: F. Yao, D. Dobkin, H. Edelsbrunner, and M. Paterson, “Partitioning space for range queries,” SIAM Journal on Computing, vol. 18, no. 2. SIAM, pp. 371–384, 1989. ista: Yao F, Dobkin D, Edelsbrunner H, Paterson M. 1989. Partitioning space for range queries. SIAM Journal on Computing. 18(2), 371–384. mla: Yao, F., et al. “Partitioning Space for Range Queries.” SIAM Journal on Computing, vol. 18, no. 2, SIAM, 1989, pp. 371–84, doi:10.1137/0218025. short: F. Yao, D. Dobkin, H. Edelsbrunner, M. Paterson, SIAM Journal on Computing 18 (1989) 371–384. date_created: 2018-12-11T12:06:50Z date_published: 1989-04-01T00:00:00Z date_updated: 2022-02-11T07:55:48Z day: '01' doi: 10.1137/0218025 extern: '1' intvolume: ' 18' issue: '2' language: - iso: eng main_file_link: - open_access: '1' url: https://epubs.siam.org/doi/10.1137/0218025 month: '04' oa: 1 oa_version: Published Version page: 371 - 384 publication: SIAM Journal on Computing publication_identifier: eissn: - 1095-7111 issn: - 0097-5397 publication_status: published publisher: SIAM publist_id: '2040' quality_controlled: '1' scopus_import: '1' status: public title: Partitioning space for range queries type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 18 year: '1989' ... --- _id: '4091' abstract: - lang: eng 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. acknowledgement: The research of this author was supported by the Amoco Foundation Facility for the Development of Computer Science 1-6-44862. article_processing_charge: No article_type: original author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Steven full_name: Skiena, Steven last_name: Skiena citation: ama: Edelsbrunner H, Skiena S. Probing convex polygons with X-Rays. SIAM Journal on Computing. 1988;17(5):870-882. doi:10.1137/0217054 apa: Edelsbrunner, H., & Skiena, S. (1988). Probing convex polygons with X-Rays. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0217054 chicago: Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” SIAM Journal on Computing. SIAM, 1988. https://doi.org/10.1137/0217054 . ieee: H. Edelsbrunner and S. Skiena, “Probing convex polygons with X-Rays,” SIAM Journal on Computing, vol. 17, no. 5. SIAM, pp. 870–882, 1988. ista: Edelsbrunner H, Skiena S. 1988. Probing convex polygons with X-Rays. SIAM Journal on Computing. 17(5), 870–882. mla: Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” SIAM Journal on Computing, vol. 17, no. 5, SIAM, 1988, pp. 870–82, doi:10.1137/0217054 . short: H. Edelsbrunner, S. Skiena, SIAM Journal on Computing 17 (1988) 870–882. date_created: 2018-12-11T12:06:53Z date_published: 1988-01-01T00:00:00Z date_updated: 2022-02-08T11:14:23Z day: '01' doi: '10.1137/0217054 ' extern: '1' intvolume: ' 17' issue: '5' language: - iso: eng main_file_link: - url: https://epubs.siam.org/doi/10.1137/0217054 month: '01' oa_version: None page: 870 - 882 publication: SIAM Journal on Computing publication_identifier: eissn: - 1095-7111 issn: - 0097-5397 publication_status: published publisher: SIAM publist_id: '2030' quality_controlled: '1' scopus_import: '1' status: public title: Probing convex polygons with X-Rays type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 17 year: '1988' ... --- _id: '4104' 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" 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 article_type: original author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Leonidas full_name: Guibas, Leonidas last_name: Guibas - first_name: Jorge full_name: Stolfi, Jorge last_name: Stolfi citation: ama: Edelsbrunner H, Guibas L, Stolfi J. Optimal point location in a monotone subdivision. SIAM Journal on Computing. 1986;15(2):317-340. doi:10.1137/0215023 apa: Edelsbrunner, H., Guibas, L., & Stolfi, J. (1986). Optimal point location in a monotone subdivision. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0215023 chicago: Edelsbrunner, Herbert, Leonidas Guibas, and Jorge Stolfi. “Optimal Point Location in a Monotone Subdivision.” SIAM Journal on Computing. SIAM, 1986. https://doi.org/10.1137/0215023. ieee: H. Edelsbrunner, L. Guibas, and J. Stolfi, “Optimal point location in a monotone subdivision,” SIAM Journal on Computing, vol. 15, no. 2. SIAM, pp. 317–340, 1986. ista: Edelsbrunner H, Guibas L, Stolfi J. 1986. Optimal point location in a monotone subdivision. SIAM Journal on Computing. 15(2), 317–340. mla: Edelsbrunner, Herbert, et al. “Optimal Point Location in a Monotone Subdivision.” SIAM Journal on Computing, vol. 15, no. 2, SIAM, 1986, pp. 317–40, doi:10.1137/0215023. short: H. Edelsbrunner, L. Guibas, J. Stolfi, SIAM Journal on Computing 15 (1986) 317–340. date_created: 2018-12-11T12:06:58Z date_published: 1986-01-01T00:00:00Z date_updated: 2022-02-01T10:05:55Z day: '01' doi: 10.1137/0215023 extern: '1' intvolume: ' 15' issue: '2' language: - iso: eng month: '01' oa_version: None page: 317 - 340 publication: SIAM Journal on Computing publication_identifier: eissn: - 1095-7111 issn: - 0097-5397 publication_status: published publisher: SIAM publist_id: '2016' quality_controlled: '1' scopus_import: '1' status: public title: Optimal point location in a monotone subdivision type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 15 year: '1986' ... --- _id: '4105' 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" 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" article_processing_charge: No article_type: original author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Joseph full_name: O'Rourke, Joseph last_name: O'Rourke - first_name: Raimund full_name: Seidel, Raimund last_name: Seidel citation: ama: Edelsbrunner H, O’Rourke J, Seidel R. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing. 1986;15(2):341-363. doi:10.1137/0215024 apa: Edelsbrunner, H., O’Rourke, J., & Seidel, R. (1986). Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0215024 chicago: Edelsbrunner, Herbert, Joseph O’Rourke, and Raimund Seidel. “Constructing Arrangements of Lines and Hyperplanes with Applications.” SIAM Journal on Computing. SIAM, 1986. https://doi.org/10.1137/0215024. ieee: H. Edelsbrunner, J. O’Rourke, and R. Seidel, “Constructing arrangements of lines and hyperplanes with applications,” SIAM Journal on Computing, vol. 15, no. 2. SIAM, pp. 341–363, 1986. 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.” SIAM Journal on Computing, vol. 15, no. 2, SIAM, 1986, pp. 341–63, doi:10.1137/0215024. short: H. Edelsbrunner, J. O’Rourke, R. Seidel, SIAM Journal on Computing 15 (1986) 341–363. date_created: 2018-12-11T12:06:58Z date_published: 1986-01-01T00:00:00Z date_updated: 2022-02-01T11:03:07Z day: '01' doi: 10.1137/0215024 extern: '1' intvolume: ' 15' issue: '2' language: - iso: eng month: '01' oa_version: None page: 341 - 363 publication: SIAM Journal on Computing publication_identifier: eissn: - 1095-7111 issn: - 0097-5397 publication_status: published publisher: SIAM publist_id: '2017' quality_controlled: '1' scopus_import: '1' status: public title: Constructing arrangements of lines and hyperplanes with applications type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 15 year: '1986' ... --- _id: '4110' 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. article_processing_charge: No article_type: original author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Emo full_name: Welzl, Emo last_name: Welzl citation: ama: Edelsbrunner H, Welzl E. Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing. 1986;15(1):271-284. doi:10.1137/0215019 apa: Edelsbrunner, H., & Welzl, E. (1986). Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0215019 chicago: Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional Arrangements with Applications.” SIAM Journal on Computing. SIAM, 1986. https://doi.org/10.1137/0215019. ieee: H. Edelsbrunner and E. Welzl, “Constructing belts in two-dimensional arrangements with applications,” SIAM Journal on Computing, vol. 15, no. 1. SIAM, pp. 271–284, 1986. ista: Edelsbrunner H, Welzl E. 1986. Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing. 15(1), 271–284. mla: Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional Arrangements with Applications.” SIAM Journal on Computing, vol. 15, no. 1, SIAM, 1986, pp. 271–84, doi:10.1137/0215019. short: H. Edelsbrunner, E. Welzl, SIAM Journal on Computing 15 (1986) 271–284. date_created: 2018-12-11T12:07:00Z date_published: 1986-01-01T00:00:00Z date_updated: 2022-02-01T09:34:20Z day: '01' doi: 10.1137/0215019 extern: '1' intvolume: ' 15' issue: '1' language: - iso: eng month: '01' oa_version: None page: 271 - 284 publication: SIAM Journal on Computing publication_identifier: eissn: - 1095-7111 issn: - 0097-5397 publication_status: published publisher: SIAM publist_id: '2014' quality_controlled: '1' scopus_import: '1' status: public title: Constructing belts in two-dimensional arrangements with applications type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 15 year: '1986' ...