{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T22:46:32Z","timestamp":1736635592571,"version":"3.32.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"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":[[1997,4]]},"DOI":"10.1007\/bf02523679","type":"journal-article","created":{"date-parts":[[2006,11,8]],"date-time":"2006-11-08T04:50:25Z","timestamp":1162961425000},"page":"380-398","source":"Crossref","is-referenced-by-count":7,"title":["On counting pairs of intersecting segments and off-line triangle range searching"],"prefix":"10.1007","volume":"17","author":[{"given":"M.","family":"Pellegrini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02523679_CR1","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF02187805","volume":"5","author":"P. K. Agarwal","year":"1990","unstructured":"[A1] P. K. Agarwal. Partitioning arrangements of lines, I: An efficient deterministic algorithm.Discrete Comput. Geom., 5:449\u2013483, 1990.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523679_CR2","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/BF02187809","volume":"5","author":"P. K. Agarwal","year":"1990","unstructured":"[A2] P. K. Agarwal. Partitioning arrangements of lines, II: Applications.Discrete Comput. Geom., 5:533\u2013573, 1990.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523679_CR3","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1137\/0219020","volume":"19","author":"P. K. Agarwal","year":"1990","unstructured":"[AS] P. K. Agarwal and M. Sharir. Red-blue intersection detection algorithms, with applications to motion planning and collision detection.SIAM J. Comput., 19:297\u2013321, 1990.","journal-title":"SIAM J. Comput."},{"key":"BF02523679_CR4","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"J. L. Bentley","year":"1979","unstructured":"[BO] J. L. Bentley and T. Ottman. Algorithms for reporting and counting geometric intersections.IEEE Trans. Comput., 28:643\u2013647, 1979.","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"BF02523679_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B. Chazelle","year":"1992","unstructured":"[CE] B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane.J. Assoc. Comput. Mach., 39(1):1\u201354, 1992.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02523679_CR6","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01182771","volume":"11","author":"B. Chazelle","year":"1994","unstructured":"[CEGS] B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Algorithms for bichromatic line segment problems and polyhedra terrains.Algorithmica, 11:116\u2013132, 1994.","journal-title":"Algorithmica"},{"issue":"3","key":"BF02523679_CR7","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B. Chazelle","year":"1990","unstructured":"[CF] B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry.Combinatorica, 10(3):229\u2013249, 1990.","journal-title":"Combinatorica"},{"key":"BF02523679_CR8","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0022-0000(86)90025-5","volume":"32","author":"B. Chazelle","year":"1986","unstructured":"[Cha1] B. Chazelle. Reporting and counting segment intersections.J. Comput. System Sci., 32:156\u2013182, 1986.","journal-title":"J. Comput. System Sci."},{"key":"BF02523679_CR9","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"[Cha2] B. Chazelle. Lower bounds on the complexity of polytope range searching.J. Amer. Math. Soc., 2:637\u2013666, 1989.","journal-title":"J. Amer. Math. Soc."},{"key":"BF02523679_CR10","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"[Cha3] B. Chazelle. Cutting hyperplanes for divide and conquer.Discrete Comput. Geom., 9:145\u2013158, 1993.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523679_CR11","doi-asserted-by":"crossref","unstructured":"[Cha4] B. Chazelle. Lower bounds for off-line range range searching.Proc. 27th ACM Symp. on Theory of Computing, pages 733\u2013740, 1995.","DOI":"10.1145\/225058.225291"},{"key":"BF02523679_CR12","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"[Cla] K. L. Clarkson. New applications of random sampling in computational geometry.Discrete Comput. Geom., 2:195\u2013222, 1987.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523679_CR13","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. Clarkson","year":"1989","unstructured":"[CS] K. Clarkson and P. Shor. Applications of random sampling in computational geometry, II.Discrete Comput. Geom., 4:387\u2013422, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523679_CR14","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01758854","volume":"8","author":"B. Chazelle","year":"1992","unstructured":"[CSW] B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems.Algorithmica, 8:407\u2013429, 1992.","journal-title":"Algorithmica"},{"key":"BF02523679_CR15","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"[CW] B. Chazelle and E. Welzl. Quasi-optimal range searching in spaces of finite VC-dimension.Discrete Comput. Geom., 4:467\u2013489, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523679_CR16","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0019-9958(84)80040-6","volume":"63","author":"R. Cole","year":"1985","unstructured":"[CY] R. Cole and C. K. Yap. Geometric retrieval problems.Inform. and Control, 63:39\u201357, 1985.","journal-title":"Inform. and Control"},{"key":"BF02523679_CR17","unstructured":"[dBS] M. de Berg and O. Schwarzkopf. Cuttings and applications. Technical Report TR CS-92-26, Department of Computer Science, Utrecht University, 1992."},{"key":"BF02523679_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"[E] H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987."},{"key":"BF02523679_CR19","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"[EOS] H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM J. Comput., 15:341\u2013363, 1986.","journal-title":"SIAM J. Comput."},{"key":"BF02523679_CR20","doi-asserted-by":"crossref","unstructured":"[ES] J. Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies.Proc. 34th Symp. on Foundations of Computer Science, pages 528\u2013536, 1993.","DOI":"10.1109\/SFCS.1993.366834"},{"issue":"2","key":"BF02523679_CR21","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1137\/0222031","volume":"22","author":"H. Edelsbrunner","year":"1993","unstructured":"[ESS] H. Edelsbrunner, R. Seidel, and M. Sharir. On the zone theorem for hyperplane arrangements.SIAM J. Comput., 22(2):418\u2013429, 1993.","journal-title":"SIAM J. Comput."},{"key":"BF02523679_CR22","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0190(86)90088-8","volume":"23","author":"H. Edelsbrunner","year":"1986","unstructured":"[EW] H. Edelsbrunner and E. Welzl. Halfplanar range search in linear space ando(n 0,695) query time.Inform. Process. Lett., 23:289\u2013293, 1986.","journal-title":"Inform. Process. Lett."},{"key":"BF02523679_CR23","volume-title":"Computer Graphics: Principles and Practice","author":"J. D. Foley","year":"1990","unstructured":"[FVFH] J. D. Foley, A. Van Dam, S. K. Feiner, and J. F. Hughes.Computer Graphics: Principles and Practice. Addison-Wesley, Reading, MA. 1990."},{"key":"BF02523679_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/3-540-19487-8_7","volume-title":"Proc. 1st Scand. Workshop on Algorithm Theory","author":"L. Guibas","year":"1988","unstructured":"[GOS] L. Guibas, M. Overmars, and M. Sharir. Intersecting line segments, ray shooting, and other applications of geometric partitioning techniques.Proc. 1st Scand. Workshop on Algorithm Theory, pages 64\u201373. Lecture Notes in Computer Science, volume 318. Springer-Verlag, Berlin, 1988."},{"key":"BF02523679_CR25","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"[HW] D. Haussler and E. Welzl. \u025b-nets and simplex range queries.Discrete Comput. Geom., 2:127\u2013151, 1987.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523679_CR26","unstructured":"[K] R. Karp. On-line algorithms versus off-line algorithms: how much is it worth to know the future? Technical Report TR-92-044, International Computer Science Institute, 1992."},{"key":"BF02523679_CR27","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/BF01759037","volume":"6","author":"F. M. Maley","year":"1991","unstructured":"[Mal] F. M. Maley. A generic algorithm for one-dimensional homotopic compactation.Algorithmica, 6:103\u2013128, 1991.","journal-title":"Algorithmica"},{"key":"BF02523679_CR28","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02574697","volume":"6","author":"J. Matou\u0161ek","year":"1991","unstructured":"[Mat1] J. Matou\u0161ek. Cutting hyperplane arrangements.Discrete Comput. Geom., 6:385\u2013406, 1991.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523679_CR29","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"[Mat2] J. Matou\u0161ek. Efficient partition trees.Discrete Comput. Geom., 8:315\u2013334, 1992.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523679_CR30","doi-asserted-by":"crossref","unstructured":"[Mat3] J. Matou\u0161ek. Range searching with efficient hierarchical cuttings.Proc. 8th ACM Symp. on Computational Geometry, pages 276\u2013285, 1992.","DOI":"10.1145\/142675.142732"},{"key":"BF02523679_CR31","volume-title":"Multidimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"[Meh] K. Mehlhorn.Multidimensional Searching and Computational Geometry, Chapter 2. Springer-Verlag, Berlin, 1984."},{"key":"BF02523679_CR32","series-title":"NATO ASI","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/978-3-642-83539-1_11","volume-title":"Theoretical Foundations of Computer Graphics and CAD","author":"H. G. Mairson","year":"1988","unstructured":"[MS] H. G. Mairson and J. Stolfi. Reporting and counting intersections between two sets of line segments. In R. A. Earnshaw, editor,Theoretical Foundations of Computer Graphics and CAD, pages 307\u2013325. NATO ASI, volume F40. Springer-Verlag, Berlin, 1988."},{"key":"BF02523679_CR33","doi-asserted-by":"crossref","unstructured":"[Mul] K. Mulmuley. A fast planar partition algorithm, I.Proc. 29th Ann. IEEE Symp. on Foundations of Computer Science, pages 580\u2013589, 1988.","DOI":"10.1109\/SFCS.1988.21974"},{"key":"BF02523679_CR34","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1145\/358656.358681","volume":"25","author":"J. Nievergelt","year":"1982","unstructured":"[NP] J. Nievergelt and F. P. Preparata. Plane-sweep algorithms for intersecting geometric figures.Comm. ACM, 25:739\u2013747, 1982.","journal-title":"Comm. ACM"},{"issue":"1","key":"BF02523679_CR35","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1137\/S0097539792229404","volume":"23","author":"M. Pellegrini","year":"1994","unstructured":"[P1] M. Pellegrini. On collision-free placements of simplices and the closest pair of lines in 3-space.SIAM J. Comput., 23(1):133\u2013153, 1994.","journal-title":"SIAM J. Comput."},{"key":"BF02523679_CR36","doi-asserted-by":"crossref","unstructured":"[P2] M. Pellegrini. On point location and motion planning in arrangements of simplices.Proc. 26th ACM Symp. on Theory of Computing, pages 95\u2013104, 1994. Journal version inSIAM J. Comput., 25(5), 1996.","DOI":"10.1145\/195058.195112"},{"key":"BF02523679_CR37","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: an Introduction","author":"F. P. Preparata","year":"1985","unstructured":"[PS1] F. P. Preparata and M. I. Shamos.Computational Geometry: an Introduction. Springer-Verlag, New York, 1985."},{"key":"BF02523679_CR38","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1137\/0220029","volume":"20","author":"J. Pach","year":"1991","unstructured":"[PS2] J. Pach and M. Sharir. On vertical visibility in arrangements of segments and the queue size in the Bentley-Ottman line sweeping algorithm.SIAM J. Comput., 20:460\u2013470, 1991.","journal-title":"SIAM J. Comput."},{"key":"BF02523679_CR39","doi-asserted-by":"crossref","unstructured":"[SH] M. I. Shamos and D. Hoey. Geometric intersection problems.Proc. 17th Ann. IEEE Symp. on Foundations of Computer Science, pages 208\u2013215, 1976.","DOI":"10.1109\/SFCS.1976.16"},{"key":"BF02523679_CR40","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1137\/0211012","volume":"11","author":"D. E. Willard","year":"1982","unstructured":"[W] D. E. Willard. Polygon retrieval.SIAM J. Comput., 11:149\u2013165, 1982.","journal-title":"SIAM J. Comput."},{"key":"BF02523679_CR41","doi-asserted-by":"crossref","unstructured":"[YY] A. C. Yao and F. F. Yao. A general approach toD-dimensional geometric queries.Proc. 17th Ann. ACM Symp. on Theory of Computing, pages 163\u2013168, 1985.","DOI":"10.1145\/22145.22163"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523679.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523679\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T22:19:52Z","timestamp":1736633992000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["BF02523679"],"URL":"https:\/\/doi.org\/10.1007\/bf02523679","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}