{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:14:01Z","timestamp":1760440441974,"version":"3.32.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1996,5,1]],"date-time":"1996-05-01T00:00:00Z","timestamp":830908800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,5]]},"DOI":"10.1007\/bf01955043","type":"journal-article","created":{"date-parts":[[2005,7,31]],"date-time":"2005-07-31T22:43:50Z","timestamp":1122849830000},"page":"428-447","source":"Crossref","is-referenced-by-count":30,"title":["Lines in space: Combinatorics and algorithms"],"prefix":"10.1007","volume":"15","author":[{"given":"B.","family":"Chazelle","sequence":"first","affiliation":[]},{"given":"H.","family":"Edelsbrunner","sequence":"additional","affiliation":[]},{"given":"L. J.","family":"Guibas","sequence":"additional","affiliation":[]},{"given":"M.","family":"Sharir","sequence":"additional","affiliation":[]},{"given":"J.","family":"Stolfi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01955043_CR1","volume-title":"Discrete and Computational Geometry: Papers from the DIMACS Special Year","author":"P. Agarwal","year":"1991","unstructured":"P. Agarwal, Geometric partitioning and its applications, inDiscrete and Computational Geometry: Papers from the DIMACS Special Year, American Mathematical Society, Providence, RI, 1991."},{"key":"BF01955043_CR2","first-page":"13","volume-title":"Lecture Notes in Computer Science, Vol. 519","author":"B. Aronov","year":"1991","unstructured":"B. Aronov, M. Pellegrini, and M. Sharir, On the zone of a surface in a hyperplane arrangement, In preparation. See alsoProc. 2nd WADS Workshop, 1991, Lecture Notes in Computer Science, Vol. 519, Springer-Verlag, Berlin, pp. 13\u201319, for an early version by two of the authors."},{"key":"BF01955043_CR3","volume-title":"Theoretical Kinematics","author":"O. Bottema","year":"1990","unstructured":"O. Bottema and B. Roth,Theoretical Kinematics, Dover, New York, 1990."},{"doi-asserted-by":"crossref","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, R. Pollack, R. Seidel, M. Sharir, and J. Snoeyink, Counting and cutting cycles of lines and line segments in space,Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990, pp. 242\u2013251.","key":"BF01955043_CR4","DOI":"10.1109\/FSCS.1990.89543"},{"unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Algorithms for bichromatic line segment problems and polyhedral terrains, In preparation. An earlier version of this paper, combined with the current paper, has appeared inProc. 21st ACM Symp. on Theory of Computing, 1989, pp. 382\u2013393.","key":"BF01955043_CR5"},{"key":"BF01955043_CR6","first-page":"179","volume-title":"Lectures Notes in Computer Science, Vol. 372","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, A singly-exponential stratification scheme for real semi-algebraic varieties and its applications,Proc. 16th ICALP Colloq., Lectures Notes in Computer Science, Vol. 372, Springer-Verlag, Berlin, 1989, pp. 179\u2013193."},{"doi-asserted-by":"crossref","unstructured":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and surfaces,Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 568\u2013579.","key":"BF01955043_CR7","DOI":"10.1109\/SFCS.1988.21973"},{"key":"BF01955043_CR8","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B. Chazelle","year":"1990","unstructured":"B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry,Combinatorica,10 (1990), 229\u2013249.","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"B. Chazelle, An optimal convex hull algorithm and new results on cuttings,Proc. 32nd Symp. on Foundations of Computer Science, 1991, pp. 29\u201338.","key":"BF01955043_CR9","DOI":"10.1109\/SFCS.1991.185345"},{"key":"BF01955043_CR10","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. Clarkson","year":"1987","unstructured":"K. Clarkson, New applications of random sampling in computational geometry,Discrete Comput. Geom.,2 (1987), 195\u2013222.","journal-title":"Discrete Comput. Geom."},{"doi-asserted-by":"crossref","unstructured":"K. Clarkson, A probabilistic algorithm for the post office problem,Proc. 17th ACM Symp. on Theory of Computing, 1985, pp. 175\u2013184.","key":"BF01955043_CR11","DOI":"10.1145\/22145.22165"},{"key":"BF01955043_CR12","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. Clarkson","year":"1989","unstructured":"K. Clarkson, Applications of random sampling in computational geometry,Discrete Comput. Geom.,4 (1989), 387\u2013421.","journal-title":"Discrete Comput. Geom."},{"key":"BF01955043_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987."},{"doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner, L. Guibas, and M. Sharir, The complexity of many faces in arrangements of lines and of segments,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 44\u201355.","key":"BF01955043_CR14","DOI":"10.1145\/73393.73399"},{"key":"BF01955043_CR15","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF02187785","volume":"5","author":"H. Edelsbrunner","year":"1990","unstructured":"H. Edelsbrunner, L. Guibas, and M. Sharir, The complexity of many faces in arrangements of planes and related problems,Discrete Comput. Geom.,5 (1990), 197\u2013216.","journal-title":"Discrete Comput. Geom."},{"unstructured":"G. Fano and A. Terracini,Lezioni di Geometria Analitica e Proiettiva, Paravia, 1939.","key":"BF01955043_CR16"},{"key":"BF01955043_CR17","volume-title":"Technical Report UCB\/CSD 88\/432","author":"Z. Gigus","year":"1988","unstructured":"Z. Gigus, J. Canny, and R. Seidel, Efficiently computing and representing aspect graphs of polyhedral objects, Technical Report UCB\/CSD 88\/432, Univesrity of California at Berkeley, August 1988."},{"key":"BF01955043_CR18","volume-title":"Methods of Algebraic Geometry","author":"W. Hodge","year":"1952","unstructured":"W. Hodge and D. Pedoe,Methods of Algebraic Geometry, Cambridge University Press, Cambridge, 1952."},{"unstructured":"K. Hunt,Kinematic Geometry of Mechanisms, Oxford, 1990.","key":"BF01955043_CR19"},{"key":"BF01955043_CR20","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler and E. Welzl, Epsilon nets and simplex range searching,Discrete Comput. Geom.,2 (1987), 127\u2013151.","journal-title":"Discrete Comput. Geom."},{"key":"BF01955043_CR21","volume-title":"Scientific Center Report G320-2711","author":"A. Inselberg","year":"1981","unstructured":"A. Inselberg,N-dimensional graphics. Part I \u2014lines and hyperplanes. Scientific Center Report G320-2711, IBM, Los Angeles, CA, 1981."},{"key":"BF01955043_CR22","volume-title":"A Treatise on the Line Complex","author":"C. M. Jessop","year":"1969","unstructured":"C. M. Jessop,A Treatise on the Line Complex, Chelsea, New York, 1969."},{"key":"BF01955043_CR23","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/BF02187804","volume":"5","author":"J. Matou\u0161ek","year":"1990","unstructured":"J. Matou\u0161ek, Construction of\u03b5-nets,Discrete Comput. Geom.,5 (1990), 427\u2013448.","journal-title":"Discrete Comput. Geom."},{"key":"BF01955043_CR24","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02574697","volume":"6","author":"J. Matou\u0161ek","year":"1991","unstructured":"J. Matou\u0161ek, Cutting hyperplane arrangements,Discrete Comput. Geom.,6 (1991), 385\u2013406.","journal-title":"Discrete Comput. Geom."},{"doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, Approximations and optimal geometric divide-and-conquer,Proc. 23rd Annual ACM Symp. on Theory of Computing, 1991, pp. 506\u2013511.","key":"BF01955043_CR25","DOI":"10.1145\/103418.103470"},{"doi-asserted-by":"crossref","unstructured":"M. McKenna, Arrangements of lines in 3-space: a data structure with applications, Ph.D. Dissertation, Johns Hopkins University, 1989.","key":"BF01955043_CR26","DOI":"10.1145\/73393.73431"},{"key":"BF01955043_CR27","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","volume":"15","author":"J. Milnor","year":"1964","unstructured":"J. Milnor. On the Betti numbers of real varieties,Proc. Amer. Math. Soc.,15 (1964), 275\u2013280.","journal-title":"Proc. Amer. Math. Soc."},{"doi-asserted-by":"crossref","unstructured":"M. McKenna and J. O'Rourke, Arrangements of lines in 3-space: a data structure with applications,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 371\u2013380.","key":"BF01955043_CR28","DOI":"10.1145\/73393.73431"},{"unstructured":"M. Paterson, Personal communication.","key":"BF01955043_CR29"},{"doi-asserted-by":"crossref","unstructured":"W. H. Plantinga and C. R. Dyer, An algorithm for constructing the aspect graph,Proc. 27th IEEE Symp. on Foundations of Computer Science, 1986, pp. 123\u2013131.","key":"BF01955043_CR30","DOI":"10.1109\/SFCS.1986.4"},{"key":"BF01955043_CR31","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1098\/rstl.1865.0017","volume":"155","author":"J. Pl\u00fccker","year":"1865","unstructured":"J. Pl\u00fccker, On a new geometry of space,Philos. Trans. Roy. Soc. London,155 (1865), 725\u2013791.","journal-title":"Philos. Trans. Roy. Soc. London"},{"key":"BF01955043_CR32","first-page":"437","volume-title":"Lecture Notes in Computer Science, Vol. 450","author":"J. Pach","year":"1990","unstructured":"J. Pach, R. Pollack, and E. Welzl, Weaving patterns of lines and line segments,Proc. 1st SIGAL Symp., Lecture Notes in Computer Science, Vol. 450, Springer-Verlag, Berlin, 1990, pp. 437\u2013446."},{"doi-asserted-by":"crossref","unstructured":"R. Seidel, Constructing higher dimensional convex hulls at logarithmic cost per face,Proc. 18th ACM Symp. on Theory of Computing, 1986, pp. 404\u2013413.","key":"BF01955043_CR33","DOI":"10.1145\/12130.12172"},{"key":"BF01955043_CR34","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/BF02574706","volume":"6","author":"M. Sharir","year":"1991","unstructured":"M. Sharir, Onk-sets in arrangements of curves and surfaces,Discrete Comput. Geom.,6 (1991), 593\u2013613.","journal-title":"Discrete Comput. Geom."},{"unstructured":"M. Sharir, On joints in arrangements of lines in space and related problems, In preparation.","key":"BF01955043_CR35"},{"key":"BF01955043_CR36","volume-title":"Analytical Geometry of Three Dimensions","author":"D. M. Y. Sommerville","year":"1987","unstructured":"D. M. Y. Sommerville,Analytical Geometry of Three Dimensions, Springer-Verlag, Heidelberg, 1987."},{"key":"BF01955043_CR37","volume-title":"Oriented Projective Geometry","author":"J. Stolfi","year":"1991","unstructured":"J. Stolfi,Oriented Projective Geometry, Academic Press, New York, 1991."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01955043.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01955043\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01955043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T21:59:23Z","timestamp":1735855163000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01955043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,5]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1996,5]]}},"alternative-id":["BF01955043"],"URL":"https:\/\/doi.org\/10.1007\/bf01955043","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1996,5]]}}}