@inproceedings{BerDobEpp-SODA-90, title = {{Visibility with a moving point of view}}, author = {Marshall W. Bern and David P. Dobkin and David Eppstein and Robert L. Grossman}, booktitle = {Proc. 1st Symp. Discrete Algorithms}, publisher = {Assoc. Comput. Mach. and Soc. Industrial {\&} Applied Mathematics}, pages = {107--118}, month = {January}, year = {1990} } @article{BerDobEpp-Algo-94, title = {{Visibility with a moving point of view}}, author = {Marshall W. Bern and David P. Dobkin and David Eppstein and Robert L. Grossman}, journal = {Algorithmica}, volume = {11}, number = {4}, pages = {360--378}, month = {April}, year = {1994}, review = {MR-94j:68307} } @article{MR-94j:68307, reviews = {BerDobEpp-Algo-94}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Visibility with a moving point of view}}, number = {94j:68307}, year = {1994} } @Article{Matousek95, title={Approximations and Optimal Geometric Divide-and-Conquer}, author={Ji{\v{r}}{\'\i} Matou{\v{s}}ek}, pages={203--208}, journal=jcss, year=1995, month=apr, volume=50, number=2, preliminary={STOC::Matousek1991} } @article{ma4, author="J. Matousek", title="Efficient partition trees", journal="Discrete and Computational Geometry", year="1992", volume="8", number="", pages="315-334" } @inproceedings{ma92acm, author="J. Matousek", title="Range searching with efficient hierarchical cuttings", booktitle="$8^{th}$ ACM Conf. in Comp. Geom.", address="Berlin", year="1992", pages="276-285" } @article {ma1, author="J. Matousek", title="Range searching with efficient hierarchical cuttings", journal="Discrete and Computational Geometry", year="1993", volume="10", number="", pages="157-182" } @inproceedings{a-rsoas-89 , author = "Pankaj K. Agarwal" , title = "Ray shooting and other applications of spanning trees with low stabbing number" , booktitle = "Proc. 5th Annu. ACM Sympos. Comput. Geom." , year = 1989 , pages = "315--325" , precedes = "a-rsoas-92" , update = "96.05 agarwal, 95.05 korneenko" } @article{a-rsoas-92 , author = "Pankaj K. Agarwal" , title = "Ray shooting and other applications of spanning trees with low stabbing number" , journal = "SIAM J. Comput." , volume = 21 , year = 1992 , pages = "540--570" , keywords = "ray shooting, visibility, spanning trees, partition trees" , succeeds = "a-rsoas-89" , update = "96.05 agarwal, 95.05 korneenko" } @TECHREPORT{duke.tr:DukeCSTR9122, AUTHOR = "Pankaj K. {Agarwal} and Jiri Matousek.", year = "1991", ABSTRACT = "\indent We present efficient algorithms for the {\em ray shooting} problem: Given a collection $\Gamma$ of objects in ${\bf R}^{d}$, build a data structure so that, for a query ray, one can quickly determine the first object of $\Gamma$ hit by the ray. Using the parametric search technique, we reduce this problem to the {\em segment emptiness} problem. For various ray shooting problems, we achieve space/query time tradeoffs of the following type: for some integer $b$ and a parameter $m \, (n \leq m \leq n^{b})$ the queries are answered in time $O(\frac{n}{m^{1/b}}\, \mbox {log} ^{O(1)}n)$, with $O(m^{1+ \epsilon })$ space and preprocessing time $(\varepsilon > 0$ is arbitrarily small but fixed constant). We get $b = \lfloor d/2 \rfloor $ for ray shooting in a convex $d$-polytope defined as an intersection of $n$ half-spaces, $b = d$ for an arrangement of $n$ hyperplanes in ${\bf R}^{d}$ and $b = 3$ for an arrangement of $n$ half-planes in ${\bf R}^{3}$. Our approach also yields fast procedures for finding the first $k$ objects hit by a query ray, for searching nearest and farthest neighbors, and for the hidden surface removal. All the data structures can be maintained dynamically in amortized time $O(m^{1+ \epsilon }/n)$ per insert/delete operation. ", LOCATION = "ftp://ftp.cs.duke.edu/dist/techreport/1991/1991-22.ps.Z", NOTE = "Printed copies available from T.R. Librarian, Dept. of Computer Science, Duke University, Box 90129, Durham, NC 27708-0129", PUBLISHER = "Department of Computer Science, Duke University", REPORTNUMBER = "Technical report DUKE--TR--1991--22", TITLE = " Ray Shooting and Parametric Search", SUBMITTER = "surendar@swift.cs.duke.edu (Mon Jul 1 23:53:45 1996)", institution = "Duke University", KEY = "DukeCSTR9122" } @inproceedings{am-rsps-92 , author = "Pankaj K. Agarwal and J. Matou{\v s}ek" , title = "Ray shooting and parametric search" , booktitle = "Proc. 24th Annu. ACM Sympos. Theory Comput." , year = 1992 , pages = "517--526" , keywords = "ray tracing, range search, intersection, partition trees" , update = "96.09 agarwal, 96.05 agarwal" } @article{as-rsacp-96i , author = "P. K. Agarwal and M. Sharir" , title = "Ray shooting amidst convex polygons in {2D}" , journal = "J. Algorithms" , volume = 21 , year = 1996 , pages = "508--519" , update = "97.03 agarwal+pocchiola+smid, 96.09 agarwal, 96.05 agarwal" } @inproceedings{as-rsacp-93 , author = "Pankaj K. Agarwal and M. Sharir" , title = "Ray Shooting Amidst Convex Polytopes in Three Dimensions" , booktitle = "Proc. 4th ACM-SIAM Sympos. Discrete Algorithms" , year = 1993 , pages = "260--270" , precedes = "as-rsacp-96ii" , update = "96.05 smid, 93.05 smid" } @inproceedings{af-acrsm-97 , author = "B. Aronov and S. Fortune" , title = "Average-Case Ray Shooting and Minimum Weight Triangulations" , booktitle = "Proc. 13th Annu. ACM Sympos. Comput. Geom." , year = 1997 , pages = "203--212" , update = "97.07 efrat" } @inproceedings{bf-gsars-90 , author = "R. Bar-Yehuda and S. Fogel" , title = "Good splitters with applications to ray shooting" , booktitle = "Proc. 2nd Canad. Conf. Comput. Geom." , year = 1990 , pages = "81--84" , keywords = "ray tracing, arrangements" } @techreport{bf-vrs-90 , author = "R. Bar-Yehuda and S. Fogel" , title = "Variations on Ray Shooting" , type = "Technical {Report}" , number = 639 , institution = "Technion IIT" , address = "Haifa, Israel" , year = 1990 , keywords = "sheaf, ES-trees" , update = "95.01 smid, 93.09 milone+mitchell" } @article{bf-vrs-94 , author = "R. Bar-Yehuda and S. Fogel" , title = "Variations on Ray Shooting" , journal = "Algorithmica" , volume = 11 , year = 1994 , pages = "133--145" , succeeds = "bf-vrs-90" , update = "95.01 smid, 94.05 matousek" } @inproceedings{bhosk-ershs-91 , author = "M. de Berg and D. Halperin and M. Overmars and J. Snoeyink and M. van Kreveld" , title = "Efficient ray shooting and hidden surface removal" , booktitle = "Proc. 7th Annu. ACM Sympos. Comput. Geom." , year = 1991 , pages = "21--30" , keywords = "ray tracing, hidden surface removal, random sampling" , cites = "as-anspt-91, ako-iqco-91, as-zasha-91, cegpsss-ccclr-90, cegs-lscaa-89, cg-vippg-89, csw-qoubs-90, cj-sersi-91, cs-vppt-89, bo-hsrap-90, de-ssio-87, dk-ladsc-85, e-acg-87, m-aodq-90, m-wcohs-87, os-oshsr-89, p-srs3d-90, p-nrrsi-91, sml-rtatp-88, s-pcg-88, ZZZ" , update = "97.11 bibrelex" } @Article{deb94, author = "M. De Berg and D. Halperin and M. Overmars and J. Snoeyink and M. Van Kreveld", title = "Efficient ray shooting and hidden surface removal", journal = "Algorithmica: An International Journal in Computer Science", volume = "12", number = "1", year = "1994", publisher = "Springer Verlag, New York", pages = "30--53", topic = "visibility", } @inproceedings{cegghss-rspug-91 , author = "B. Chazelle and H. Edelsbrunner and M. Grigni and L. Guibas and J. Hershberger and M. Sharir and J. Snoeyink" , title = "Ray shooting in polygons using geodesic triangulations" , booktitle = "Proc. 18th Internat. Colloq. Automata Lang. Program." , series = "Lecture Notes Comput. Sci." , volume = 510 , publisher = "Springer-Verlag" , year = 1991 , pages = "661--673" , keywords = "ray shooting, simple polygon, geodesics" , update = "93.09 rote" } @article{cegghss-rspug-94 , author = "B. Chazelle and H. Edelsbrunner and M. Grigni and L. Guibas and J. Hershberger and M. Sharir and J. Snoeyink" , title = "Ray shooting in polygons using geodesic triangulations" , journal = "Algorithmica" , volume = 12 , year = 1994 , pages = "54--68" , keywords = "ray shooting, simple polygon, geodesics" , succeeds = "cegghss-rspug-91" , update = "96.05 pocchiola+ramkumar" } @article{cf-plhur-94 , author = "B. Chazelle and J. Friedman" , title = "Point Location among Hyperplanes and Unidirectional Ray-Shooting" , journal = "Comput. Geom. Theory Appl." , volume = 4 , year = 1994 , pages = "53--62" , update = "97.11 bibrelex, 95.01 matousek+smid" } @article{cj-arsis-92 , author = "S. W. Cheng and R. Janardan" , title = "Algorithms for ray-shooting and intersection searching" , journal = "J. Algorithms" , volume = 13 , year = 1992 , pages = "670--692" , update = "93.09 smid" } @inproceedings{cj-sersi-91 , author = "S. W. Cheng and R. Janardan" , title = "Space-efficient ray shooting and intersection searching: algorithms, dynamization and applications" , booktitle = "Proc. 2nd ACM-SIAM Sympos. Discrete Algorithms" , year = 1991 , pages = "7--16" , keywords = "ray tracing, dynamization, spanning trees of low stabbing number" } @inproceedings{cpt-uadpl-93 , author = "Y.-J. Chiang and F. P. Preparata and R. Tamassia" , title = "A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps" , booktitle = "Proc. 4th ACM-SIAM Sympos. Discrete Algorithms" , year = 1993 , pages = "44--53" , precedes = "cpt-uadpl-96" , update = "96.05 smid, 93.05 smid" } @article{cpt-uadpl-96 , author = "Y.-J. Chiang and F. P. Preparata and R. Tamassia" , title = "A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps" , journal = "SIAM J. Comput." , volume = 25 , year = 1996 , pages = "207--233" , url = "http://www.cs.brown.edu/cgc/papers/cpt-uadpl-96.ps.gz" , succeeds = "cpt-uadpl-93" , update = "97.03 tamassia, 96.05 smid, 95.01 tamassia" } @article{g-airsm-97 , author = "M. T. Goodrich" , title = "An improved ray shooting method for constructive solid geometry models via tree contraction" , journal = "Internat. J. Comput. Geom. Appl." , volume = "??" , year = 1997 , note = "to appear" , update = "97.03 tamassia" } @article{gt-drssp-97 , author = "M. T. Goodrich and R. Tamassia" , title = "Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations" , journal = "J. Algorithms" , volume = 23 , year = 1997 , pages = "51--73" , update = "97.07 smid" } @inproceedings{gt-drssp-93 , author = "M. T. Goodrich and R. Tamassia" , title = "Dynamic ray shooting and shortest paths via balanced geodesic triangulations" , booktitle = "Proc. 9th Annu. ACM Sympos. Comput. Geom." , year = 1993 , pages = "318--327" , update = "93.09 jones" } @inproceedings{gos-ilsrs-88 , author = "L. Guibas and M. Overmars and M. Sharir" , title = "Intersecting line segments, ray shooting, and other applications of geometric partitioning techniques" , booktitle = "Proc. 1st Scand. Workshop Algorithm Theory" , series = "Lecture Notes Comput. Sci." , volume = 318 , publisher = "Springer-Verlag" , year = 1988 , pages = "64--73" } @techreport{gos-rsipl-89 , author = "L. Guibas and M. Overmars and M. Sharir" , title = "Ray shooting, implicit point location, and related queries in arrangements of segments" , type = "Report" , number = 433 , institution = "Dept. Comput. Sci., New York Univ." , address = "New York, NY" , month = mar , year = 1989 , keywords = "random sampling, ray tracing, arrangements, point location" } @article{k-3vrs2-?? , author = "M. J. Katz" , title = "{3-D} vertical ray shooting and {2-D} point enclosure, range searching, and arc shooting amidst convex fat objects" , journal = "Comput. Geom. Theory Appl." , note = "to appear" , succeeds = "k-3vrs2-95" , update = "97.11 katz" , year = "1995" } @techreport{k-3vrs2-95 , author = "M. J. Katz" , title = "{3-D} vertical ray shooting and {2-D} point enclosure, range searching, and arc shooting amidst convex fat objects" , type = "Research {Report}" , number = 2583 , institution = "INRIA" , address = "BP93, 06902 Sophia-Antipolis, France" , year = 1995 , update = "97.11 katz, 96.09 smid" } @article{ms-rscp-93 , author = "J. Matou{\v s}ek and O. Schwarzkopf" , title = "On ray shooting in convex polytopes" , journal = "Discrete Comput. Geom." , volume = 10 , number = 2 , year = 1993 , pages = "215--232" , keywords = "ray shooting, convex polytope, range searching" , comments = "another part of the results of the conference version is in m-loq-93" , succeeds = "ms-loq-92" , update = "96.09 agarwal, 94.05 schwarzkopf, 94.01 matousek" } @inproceedings{mms-qsrs-94 , author = "J. S. B. Mitchell and D. M. Mount and S. Suri" , title = "Query-Sensitive Ray Shooting" , booktitle = "Proc. 10th Annu. ACM Sympos. Comput. Geom." , year = 1994 , pages = "359--368" , update = "94.09 jones, 94.01 jones" } @techreport{p-nrrsi-91 , author = "M. Pellegrini" , title = "New results on ray-shooting and isotopy classes of lines in $3$-dimensional space" , year = 1991 , update = "97.11 bibrelex" } @inproceedings{p-rsicl-91 , author = "M. Pellegrini" , title = "Ray-shooting and isotopy classes of lines in $3$-dimensional space" , booktitle = "Proc. 2nd Workshop Algorithms Data Struct." , series = "Lecture Notes Comput. Sci." , volume = 519 , publisher = "Springer-Verlag" , year = 1991 , pages = "20--31" , keywords = "ray tracing, random sampling" } @incollection{p-rsls-97 , author = "M. Pellegrini" , title = "Ray shooting and lines in space" , chapter = 32 , editor = "Jacob E. Goodman and Joseph O'Rourke" , booktitle = "Handbook of Discrete and Computational Geometry" , publisher = "CRC Press LLC" , address = "Boca Raton, FL" , year = 1997 , pages = "599--614" , update = "97.11 orourke" } @article{p-rst3s-93 , author = "M. Pellegrini" , title = "Ray shooting on triangles in $3$-space" , journal = "Algorithmica" , volume = 9 , year = 1993 , pages = "471--494" , update = "94.05 matousek" } @inproceedings{p-srs3d-90 , author = "M. Pellegrini" , title = "Stabbing and ray shooting in $3$-dimensional space" , booktitle = "Proc. 6th Annu. ACM Sympos. Comput. Geom." , year = 1990 , pages = "177--186" , cites = "a-dapal-89, a-rsoas-89, ak-frtrc-87, aw-alts-87, bdeg-vmpv-90, cegs-lscaa-89, c-narsc-87, cs-vppt-86, e-acg-87, egs-cmfal-88, emprww-sls-82, eos-calha-86, g-rt-89, gos-rsipl-89, hp-mag-52, hs-ndssg-86, jk-spals-88, m-ai-70, mo-al3sd-88, os-oshsr-89, s-chdch-86, sml-rtatp-88, s-agtd-51, s-pcg-88, ZZZ" , update = "97.11 bibrelex" } @inproceedings{s-rscp-92 , author = "O. Schwarzkopf" , title = "Ray shooting in convex polytopes" , booktitle = "Proc. 8th Annu. ACM Sympos. Comput. Geom." , year = 1992 , pages = "286--295" , precedes = "s-dmcpr-92" , cites = "aesw-emstb-90, am-dhsrr-91, am-rsps-92, bc-hhihr-92, bdsty-arsol-92, bdt-riach-, cegs-sessr-89, cf-plhur-94, c-hsh-85, c-narsc-87, c-racpq-88, cms-frric-92i, cs-arscg-89, dmt-fddtl-92, e-acg-87, gks-ricdv-92, m-ept-91, m-rph-91, m-fppa1-88, m-rmstd-91, m-rmstf-91, m-rmstl-91, s-dmgsm-91, s-sdlpc-91, s-sfira-91, ZZZ" , update = "97.11 bibrelex, 93.05 schwarzkopf" } @TECHREPORT{duke.tr:DukeCSTR9107, AUTHOR = "Pankaj K. {Agarwal} and Micha Sharir.", year = "1991", ABSTRACT = "\indent We present several applications of a recent space partitioning technique of Chazelle, Sharir and Welzl [13]. Our results include efficient algorithms for output-sensitive hidden surface removal, for ray shooting in two and three dimensions, and for constructing spanning trees with low stabbing number.", LOCATION = "ftp://ftp.cs.duke.edu/dist/techreport/1991/1991-07.ps.Z", NOTE = "Printed copies available from T.R. Librarian, Dept. of Computer Science, Duke University, Box 90129, Durham, NC 27708-0129", PUBLISHER = "Department of Computer Science, Duke University", REPORTNUMBER = "Technical report DUKE--TR--1991--07", TITLE = " Applications of a New Space Partitioning Technique", SUBMITTER = "surendar@swift.cs.duke.edu (Mon Jul 1 23:53:07 1996)", institution = "Duke University", KEY = "DukeCSTR9107" } @article{ dk-ladsc-85, info="81" , author = "D. P. Dobkin and D. G. Kirkpatrick" , title = "A linear algorithm for determining the separation of convex polyhedra" , journal = "J. Algorithms" , volume = 6 , year = 1985 , pages = "381--392" , keywords = "design of algorithms, construction, separation, convex, polyhedra, hierarchical representations" } @InProceedings{dadoun85a, author = "Nou Dadoun and David G. Kirkpatrick and John P. Walsh", title = "The Geometry of Beam Tracing", booktitle = "Proceedings of the ACM Symposium on Computational Geometry", pages = "55--61", year = "1985", month = jun, annote = "the use of BSP trees and hierarchical bounding volumes for fast beam intersection testing. \\ A solution to the hidden surface elimination problem called beam tracing is described. Beam tracing is related to ray tracing but uses spatial coherence within the scene, and area coherence within the image to batch computations. Beam tracing is an object space solution to the hidden surface problem. \\ Beam tracing is formulated in terms of its principal subprocesses: intersection, sorting, and clipping. A hierarchical scene representation is proposed. This incorporates the space decomposition idea of the BSP tree [Fuchs, Kedem, and Naylor, 80] along with the convex polytope intersection detection technique of [Dobkin and Kirkpatrick, 83] to interleave and efficiently solve the intersection and sorting subproblems of beam tracing.", } @InProceedings{dAmore:1992:OBP, author = "F. d'Amore and P. G. Franciosa", title = "On the optimal binary plane partition for sets of isothetic rectangles", booktitle = "Proc. 4th Canad. Conf. Comput. Geom.", year = "1992", pages = "1--5", } @inproceedings{bgo-pbsp-93 , author = "M. de Berg and M. de Groot and M. Overmars" , title = "Perfect binary space partitions" , booktitle = "Proc. 5th Canad. Conf. Comput. Geom." , site = "Waterloo, Canada" , year = 1993 , pages = "109--114" , precedes = "bgo-pbsp-97" , update = "97.03 devillers, 93.09 milone+mitchell" } @inproceedings{bgo-nrbsp-94 , author = "M. de Berg and M. de Groot and M. Overmars" , title = "New results on binary space partitions in the plane" , booktitle = "Proc. 4th Scand. Workshop Algorithm Theory" , series = "Lecture Notes Comput. Sci." , volume = 824 , publisher = "Springer-Verlag" , year = 1994 , pages = "61--72" , update = "95.01 schwarzkopf+smid, 94.05 schwarzkopf" } @article{bgo-pbsp-97 , author = "M. de Berg and M. de Groot and M. Overmars" , title = "Perfect binary space partitions" , journal = "Comput. Geom. Theory Appl." , volume = 7 , year = 1997 , pages = "81--91" , succeeds = "bgo-pbsp-93" , update = "97.03 devillers" } @inproceedings{b-lsbsp-95 , author = "Mark de Berg" , title = "Linear Size Binary Space Partitions for Fat Objects" , booktitle = "Proc. 3rd Annu. European Sympos. Algorithms" , series = "Lecture Notes Comput. Sci." , volume = 979 , publisher = "Springer-Verlag" , year = 1995 , pages = "252--263" , update = "97.03 murali+schwarzkopf" } @article{ekltmmv-rcerr-91 , author = "J. L. Ellis and G. Kedem and T. C. Lyerly and D. G. Thielman and R. J. Marisa and J. P. Menon and H. B. Voelcker" , title = "The ray casting engine and ray representations: a technical summary" , journal = "Internat. J. Comput. Geom. Appl." , volume = 1 , number = 4 , year = 1991 , pages = "347--380" , keywords = "mechanical CAD CAM, solid modeling, parallel computation, ray representation" } @article{py-ebsph-90 , author = "M. S. Paterson and F. F. Yao" , title = "Efficient binary space partitions for hidden-surface removal and solid modeling" , journal = "Discrete Comput. Geom." , volume = 5 , year = 1990 , pages = "485--503" , succeeds = "py-bpahs-89" } @inproceedings{py-obspo-90 , author = "M. S. Paterson and F. F. Yao" , title = "Optimal binary space partitions for orthogonal objects" , booktitle = "Proc. 1st ACM-SIAM Sympos. Discrete Algorithms" , year = 1990 , pages = "100--106" , precedes = "py-obspo-92" } @article{py-obspo-92 , author = "M. S. Paterson and F. F. Yao" , title = "Optimal binary space partitions for orthogonal objects" , journal = "J. Algorithms" , volume = 13 , year = 1992 , pages = "99--113" , succeeds = "py-obspo-90" } @TechReport{Kreveld:1992:NRD, author = "M. J. van Kreveld", title = "New results on data structures in computational geometry", type = "Ph.{D}. {Dissertation}", institution = "Dept. Comput. Sci., Univ. Utrecht", address = "Utrecht, Netherlands", year = "1992", keywords = "doctoral thesis", } @Article{Vanecek:1991:BIM, author = "G. {Vanecek, Jr.}", title = "Brep-index: a multidimensional space partitioning tree", journal = "Internat. J. Comput. Geom. Appl.", volume = "1", number = "3", year = "1991", pages = "243--261", keywords = "classification, Brep, BSP tree, data structures", } @inproceedings{bg-bspsc-94 , author = "M. de Berg and M. de Groot" , title = "Binary space partitions for sets of cubes" , booktitle = "Abstracts 10th European Workshop Comput. Geom." , nickname = "CG'94" , year = 1994 , pages = "84--88" , update = "94.05 schwarzkopf" } @article{vko91, author="M. van Kreveld and H. Overmars", title="Divided k-d Trees", journal="Algorithmica", year="1991", volume="6", number="", pages="840-858" }