{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:04:59Z","timestamp":1740107099630,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"9-11","license":[{"start":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T00:00:00Z","timestamp":1623801600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T00:00:00Z","timestamp":1623801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Vis Comput"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s00371-021-02185-4","type":"journal-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T21:02:43Z","timestamp":1623877363000},"page":"2461-2472","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Stripped halfedge data structure for parallel computation of arrangements of segments"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1580-5517","authenticated-orcid":false,"given":"Guillaume","family":"Damiand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Coeurjolly","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Bourquat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,16]]},"reference":[{"key":"2185_CR1","unstructured":"Agarwal, P.K., Sharir, M.: Arrangements and their applications. In: J.R. Sack, J.\u00a0Urrutia (eds.) Handbook of Computational Geometry, chap.\u00a02, pp. 49\u2013119. North-Holland, Amsterdam (2000)"},{"issue":"1\u20134","key":"2185_CR2","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF01762120","volume":"3","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Chazelle, B., Guibas, L., \u00d3\u2019D\u00fanlaing, C., Yap, C.: Parallel computational geometry. Algorithmica 3(1\u20134), 293\u2013327 (1988)","journal-title":"Algorithmica"},{"issue":"2","key":"2185_CR3","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/BF01941684","volume":"15","author":"R Anderson","year":"1996","unstructured":"Anderson, R., Beanie, P., Brisson, E.: Parallel algorithms for arrangements. Algorithmica 15(2), 104\u2013125 (1996)","journal-title":"Algorithmica"},{"key":"2185_CR4","doi-asserted-by":"crossref","unstructured":"Atallah, M.J., Goodrich, M.T.: Efficient plane sweeping in parallel. In: Proc. of second annual symposium on Computational geometry, pp. 216\u2013225 (1986)","DOI":"10.1145\/10515.10539"},{"key":"2185_CR5","doi-asserted-by":"crossref","unstructured":"Balaban, I.J.: An optimal algorithm for finding segments intersections. In: Proc. of Eleventh Annual Symposium on Computational Geometry, SCG\u201995, pp. 211\u2013219. Association for Computing Machinery, New York, NY, USA (1995)","DOI":"10.1145\/220279.220302"},{"key":"2185_CR6","first-page":"589","volume":"44","author":"B Baumgart","year":"1975","unstructured":"Baumgart, B.: A polyhedron representation for computer vision. Proc. AFIPS National Comput. Conf. 44, 589\u2013596 (1975)","journal-title":"Proc. AFIPS National Comput. Conf."},{"issue":"9","key":"2185_CR7","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"JL Bentley","year":"1979","unstructured":"Bentley, J.L., Ottmann, T.A.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. 28(9), 643\u2013647 (1979)","journal-title":"IEEE Trans. Comput."},{"key":"2185_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., van Kreveld, M., Overmars, M.H., Cheong, O.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer-Verlag, Berlin, Germany (2008)","edition":"3"},{"key":"2185_CR9","doi-asserted-by":"crossref","unstructured":"Biljecki, F., Ledoux, H., Du, X., Stoter, J., Soon, K.H., Khoo, V.H.S.: The most common geometric and semantic errors in CityGML datasets. ISPRS Ann. Photogramm. Remote Sens. Spatial Inf. Sci. IV-2\/W1, 13\u201322 (2016)","DOI":"10.5194\/isprs-annals-IV-2-W1-13-2016"},{"volume-title":"Effective Computational Geometry for Curves and Surfaces","year":"2006","key":"2185_CR10","unstructured":"Boissonnat, J.D., Teillaud, M. (eds.): Effective Computational Geometry for Curves and Surfaces. Springer-Verlag, Berlin Heidelberg (2006)"},{"key":"2185_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172998","volume-title":"Algorithmic Geometry","author":"JD Boissonnat","year":"1998","unstructured":"Boissonnat, J.D., Yvinec, M.: Algorithmic Geometry. Cambridge University Press, Cambridge, UK (1998)"},{"key":"2185_CR12","doi-asserted-by":"crossref","unstructured":"Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., L\u00e9vy, B.: Polygon Mesh Processing. AK Peters (2010)","DOI":"10.1201\/b10688"},{"key":"2185_CR13","unstructured":"Br\u00f6nnimann, H., Fabri, A., Giezeman, G.J., Hert, S., Hoffmann, M., Kettner, L., Pion, S., Schirra, S.: 2D and 3D linear geometry kernel. In: CGAL User and Reference Manual, 5.0.2 edn. CGAL Editorial Board (2020). https:\/\/doc.cgal.org\/5.0.2\/Manual\/packages.html#PkgKernel23"},{"issue":"1","key":"2185_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B Chazelle","year":"1992","unstructured":"Chazelle, B., Edelsbrunner, H.: An optimal algorithm for intersecting line segments in the plane. J. ACM 39(1), 1\u201354 (1992)","journal-title":"J. ACM"},{"key":"2185_CR15","doi-asserted-by":"crossref","unstructured":"Damiand, G., Lienhardt, P.: Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing. A K Peters\/CRC Press (2014)","DOI":"10.1201\/b17403"},{"key":"2185_CR16","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0925-7721(01)00050-5","volume":"22","author":"O Devillers","year":"2002","unstructured":"Devillers, O., Fronville, A., Mourrain, B., Teillaud, M.: Algebraic methods and arithmetic filtering for exact predicates on circle arcs. Comput. Geom. 22, 119\u2013142 (2002)","journal-title":"Comput. Geom."},{"key":"2185_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin Heidelberg, Berlin, Germany (1987)"},{"key":"2185_CR18","doi-asserted-by":"crossref","unstructured":"Fogel, E., Halperin, D., Wein, R.: CGAL Arrangements and Their Applications - A Step-by-Step Guide., Geometry and computing, vol.\u00a07. Springer (2012)","DOI":"10.1007\/978-3-642-17283-0"},{"issue":"4","key":"2185_CR19","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1137\/0220047","volume":"20","author":"MT Goodrich","year":"1991","unstructured":"Goodrich, M.T.: Intersecting line segments in parallel with an output-sensitive number of processors. SIAM J. Comput. 20(4), 737\u2013755 (1991)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2185_CR20","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/BF01941685","volume":"15","author":"MT Goodrich","year":"1996","unstructured":"Goodrich, M.T., Ghouse, M.R., Bright, J.: Sweep methods for parallel computational geometry. Algorithmica 15(2), 126\u2013153 (1996)","journal-title":"Algorithmica"},{"key":"2185_CR21","unstructured":"Gr\u00fcnbaum, B.: Convex Polytopes. New York, NY (1967)"},{"key":"2185_CR22","doi-asserted-by":"crossref","unstructured":"Gryaditskaya, Y., Sypesteyn, M., Hoftijzer, J.W., Pont, S., Durand, F., Bousseau, A.: Opensketch: A richly-annotated dataset of product design sketches. ACM Transactions on Graphics (Proc. SIGGRAPH Asia) 38 (2019)","DOI":"10.1145\/3355089.3356533"},{"key":"2185_CR23","doi-asserted-by":"crossref","unstructured":"Hershberger, J.: Stable snap rounding. In: Proc. of twenty-seventh annual symposium on Computational geometry, pp. 197\u2013206 (2011)","DOI":"10.1145\/1998196.1998226"},{"key":"2185_CR24","volume-title":"Geometric and Solid Modeling: An Introduction","author":"CM Hoffmann","year":"1989","unstructured":"Hoffmann, C.M.: Geometric and Solid Modeling: An Introduction. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1989)"},{"issue":"3","key":"2185_CR25","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1142\/S0218195994000173","volume":"4","author":"P Lienhardt","year":"1994","unstructured":"Lienhardt, P.: N-Dimensional generalized combinatorial maps and cellular quasi-manifolds. Inte. J. Comput. Geom. Appl. 4(3), 275\u2013324 (1994)","journal-title":"Inte. J. Comput. Geom. Appl."},{"key":"2185_CR26","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s10707-016-0277-7","volume":"21","author":"M McKenney","year":"2017","unstructured":"McKenney, M., Frye, R., Dellamano, M., Anderson, K., Harris, J.: Multi-core parallelism for plane sweep algorithms as a foundation for gis operations. GeoInformatica 21, 151\u2013174 (2017)","journal-title":"GeoInformatica"},{"key":"2185_CR27","doi-asserted-by":"crossref","unstructured":"McKenney, M., McGuire, T.: A parallel plane sweep algorithm for multi-core systems. In: Proc. of 17th ACM SIGSPATIAL international conference on advances in geographic information systems, pp. 392\u2013395 (2009)","DOI":"10.1145\/1653771.1653827"},{"key":"2185_CR28","doi-asserted-by":"crossref","unstructured":"Muller, D., Preparata, F.: Finding the intersection of two convex polyhedra. Theoret. Comput. Sci. 7(2), 217\u2013236 (1978)","DOI":"10.1016\/0304-3975(78)90051-8"},{"issue":"4","key":"2185_CR29","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.scico.2010.09.003","volume":"76","author":"S Pion","year":"2011","unstructured":"Pion, S., Fabri, A.: A Generic Lazy Evaluation Scheme for Exact Geometric Computations. Sci. Comput. Program. 76(4), 307\u2013323 (2011)","journal-title":"Sci. Comput. Program."},{"key":"2185_CR30","unstructured":"Rossignac, J.: 3D compression made simple: Edgebreaker with zipandwrap on a corner-table. In: Proc. of International Conference on Shape Modeling and Applications, pp. 278\u2013283 (2001)"},{"key":"2185_CR31","doi-asserted-by":"crossref","unstructured":"Shewchuk, J.R.: Robust adaptive floating-point geometric predicates. In: Proc. of Twelfth Annual Symposium on Computational Geometry, SCG \u201996, p. 141\u2013150. Association for Computing Machinery, New York, NY, USA (1996)","DOI":"10.1145\/237218.237337"},{"key":"2185_CR32","doi-asserted-by":"crossref","unstructured":"Sieger, D., Botsch, M.: Design, implementation, and evaluation of the surface\\_mesh data structure. In: W.R. Quadros (ed.) Proc. of 20th International Meshing Roundtable, pp. 533\u2013550. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)","DOI":"10.1007\/978-3-642-24734-7_29"},{"key":"2185_CR33","unstructured":"The CGAL Project: CGAL User and Reference Manual, 5.0.1 edn. CGAL Editorial Board (2020). https:\/\/doc.cgal.org\/5.0.1\/Manual\/packages.html"},{"issue":"1","key":"2185_CR34","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1109\/MCG.1985.276271","volume":"5","author":"K Weiler","year":"1985","unstructured":"Weiler, K.: Edge-based data structures for solid modelling in curved-surface environments. Comput. Graph. Appl. 5(1), 21\u201340 (1985)","journal-title":"Comput. Graph. Appl."},{"key":"2185_CR35","unstructured":"Wein, R., Berberich, E., Fogel, E., Halperin, D., Hemmer, M., Salzman, O., Zukerman, B.: 2D arrangements. In: CGAL User and Reference Manual, 5.0.1 edn. CGAL Editorial Board (2020). https:\/\/doc.cgal.org\/5.0.1\/Manual\/packages.html#PkgArrangementOnSurface2"},{"key":"2185_CR36","unstructured":"Wolff, M.: Heaptrack: A heap memory profiler for linux (2017). https:\/\/github.com\/KDE\/heaptrack"}],"container-title":["The Visual Computer"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-021-02185-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00371-021-02185-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-021-02185-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T14:11:23Z","timestamp":1630419083000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00371-021-02185-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,16]]},"references-count":36,"journal-issue":{"issue":"9-11","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["2185"],"URL":"https:\/\/doi.org\/10.1007\/s00371-021-02185-4","relation":{},"ISSN":["0178-2789","1432-2315"],"issn-type":[{"type":"print","value":"0178-2789"},{"type":"electronic","value":"1432-2315"}],"subject":[],"published":{"date-parts":[[2021,6,16]]},"assertion":[{"value":"28 May 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}