caa a22 4500 465821162 CHVBK 20180323112136.0 cr unu---uuuuu 170327e19900901xx s 000 0 eng 10.1007/BF01931656 doi (NATIONALLICENCE)springer-10.1007/BF01931656 Storing line segments in partition trees [Elektronische Daten] [Mark Overmars, Haijo Schipper, Micha Sharir] We design two variants of partition trees, calledsegment partition trees andinterval partition trees, that can be used for storing arbitrarily oriented line segments in the plane in an efficient way. The raw structures useO(n logn) andO(n) storage, respectively, and their construction time isO(n logn). In our applications we augment these structures by certain (simple) auxiliary structures, which may increase the storage and preprocessing time by a polylogarithmic factor. It is shown how to use these structures for solving line segment intersection queries, triangle stabbing queries and ray shooting queries in reasonably efficient ways. If we use the conjugation tree as the underlying partition tree, the query time for all problems isO(n λ), whereγ=log2(1+√5)−1≈0.695. The techniques are fairly simple and easy to understand. BIT Foundations, 1990 F 2.2 nationallicence E 2 nationallicence Overmars Mark Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, the Netherlands aut Schipper Haijo Department of Computer Science, University of Groningen, P.O. Box 800, 97000 AV, Groningen, the Netherlands aut Sharir Micha Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, 10012, New York, N.Y., USA aut BIT Numerical Mathematics Kluwer Academic Publishers 30/3(1990-09-01), 385-403 0006-3835 30:3<385 1990 30 10543 https://doi.org/10.1007/BF01931656 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01931656 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Overmars Mark Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, the Netherlands aut NATIONALLICENCE 700 1- Schipper Haijo Department of Computer Science, University of Groningen, P.O. Box 800, 97000 AV, Groningen, the Netherlands aut NATIONALLICENCE 700 1- Sharir Micha Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, 10012, New York, N.Y., USA aut NATIONALLICENCE 773 0- BIT Numerical Mathematics Kluwer Academic Publishers 30/3(1990-09-01), 385-403 0006-3835 30:3<385 1990 30 10543 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer