{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:59:48Z","timestamp":1725494388445},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540423065"},{"type":"electronic","value":"9783540477389"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-47738-1_28","type":"book-chapter","created":{"date-parts":[[2007,11,6]],"date-time":"2007-11-06T17:52:49Z","timestamp":1194371569000},"page":"292-307","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the complexity of the union of geometric objects"],"prefix":"10.1007","author":[{"given":"J\u00e1nos","family":"Pach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,9,20]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0925-7721(95)00005-8","volume":"5","author":"P. Agarwal","year":"1995","unstructured":"P. Agarwal, M. Katz, and M. Sharir: Computing depth order and related problems, Comput. Geom. Theory Appl.\n                           5 (1995), 187\u2013206.","journal-title":"Comput. Geom. Theory Appl."},{"key":"28_CR2","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1007\/s4540010064","volume":"24","author":"P. Agarwal","year":"2000","unstructured":"P. Agarwal and M. Sharir: Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions, Discrete Comput. Geom.\n                           24 (2000), 645\u2013685.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/BFb0054379","volume-title":"Algorithm Theory, SWAT\u201998 (Stockholm)","author":"B. Aronov","year":"1998","unstructured":"B. Aronov, A. Efrat, D. Halperin, and M. Sharir: On the number of regular vertices of the union of Jordan regions, in: Algorithm Theory, SWAT\u201998 (Stockholm), Lecture Notes in Comput. Sci.\n                           1432, Springer-Verlag, Berlin, 1998, 322\u2013334."},{"key":"28_CR4","doi-asserted-by":"publisher","first-page":"1785","DOI":"10.1137\/S0097539794266602","volume":"26","author":"B. Aronov","year":"1997","unstructured":"B. Aronov and M. Sharir: On translational motion planning of a convex polyhedron in 3-space, SIAM J. Comput.\n                           26 (1997), 1785\u20131803.","journal-title":"SIAM J. Comput."},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1016\/0898-1221(85)90105-1","volume":"11","author":"M. Atallah","year":"1985","unstructured":"M. Atallah: Some dynamic computational geometry problems, Computers and Mathematics with Applications\n                           11 (1985), 1171\u20131181.","journal-title":"Computers and Mathematics with Applications"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"M. de Berg, M. Katz, F. van der Stappen, and J. Vleugels: Realistic input models for geometric algorithms, in: Proc. 13th Annual Symposium on Computational Geometry, ACM Press, 1997, 294\u2013303.","DOI":"10.1145\/262839.262986"},{"key":"28_CR7","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"C-28","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley and T. A. Ottmann: Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput.\n                           C-28 (1979), 643\u2013647.","journal-title":"IEEE Trans. Comput."},{"key":"28_CR8","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/PL00009366","volume":"19","author":"J.-D. Boissonnat","year":"1998","unstructured":"J.-D. Boissonnat, M. Sharirs, B. Tagansky, and M. Yvines: Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Discrete Comput. Geom.\n                           19 (1998), 485\u2013519.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR9","doi-asserted-by":"crossref","first-page":"135","DOI":"10.4064\/fm-23-1-135-142","volume":"23","author":"Ch. Chojnacki","year":"1934","unstructured":"Ch. Chojnacki (A. Hanani): \u00dcber wesentlich unpl\u00e4ttbare Kurven im dreidimensionalen Raume, Fund. Math.\n                           23 (1934), 135\u2013142.","journal-title":"Fund. Math."},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02187783","volume":"5","author":"K. Clarkson","year":"1990","unstructured":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl: Combinational complexity bounds for arrangements of curves and surfaces, Discrete and Computational Geometry\n                           5 (1990), 99\u2013160.","journal-title":"Discrete and Computational Geometry"},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/BF02187745","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, and J. Snoeyink: On arrangements of Jordan arcs with three intersections per pair, Discrete Comput. Geom.\n                           4 (1989), 523\u2013539.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"A. Efrat: The complexity of the union of (\u03b1 \u03b2)-covered objects, Proceedings of the 15th Annual Symposium on Computational Geometry, ACM Press, 1999, 134\u2013142.","DOI":"10.1145\/304893.304958"},{"key":"28_CR13","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0925-7721(99)00036-X","volume":"14","author":"A. Efrat","year":"1999","unstructured":"A. Efrat and M. J. Katz: On the union of k-curved objects. Comput. Geom. Theory Appl.\n                           14 (1999), 241\u2013254.","journal-title":"Comput. Geom. Theory Appl."},{"key":"28_CR14","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0925-7721(93)90018-2","volume":"3","author":"A. Efrat","year":"1993","unstructured":"A. Efrat, G. Rote, and M. Sharir: On the union of fat wedges and separating a collection of segments by a line, Comput. Geom. Theory Appl.\n                           3 (1993), 277\u2013288.","journal-title":"Comput. Geom. Theory Appl."},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/PL00009494","volume":"23","author":"A. Efrat","year":"2000","unstructured":"A. Efrat and M. Sharir: On the complexity of the union of fat convex objects in the plane, Discrete Comput. Geom.\n                           23 (2000), 171\u2013189.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR16","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02759942","volume":"2","author":"P. Erd\u00f6s","year":"1964","unstructured":"P. Erd\u00f6s: On extremal problems of graphs and hypergraphs, Israel J. Math.\n                           2 (1964), 183\u2013190.","journal-title":"Israel J. Math."},{"key":"28_CR17","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/978-3-642-58043-7_2","volume-title":"New Trends in Discrete and Computational Geometry","author":"L. Guibas","year":"1993","unstructured":"L. Guibas and M. Sharir: Combinatorics and algorithms of arrangements, in: New Trends in Discrete and Computational Geometry (J. Pach, ed.), Springer-Verlag, Berlin, 1993, 9\u201336."},{"key":"28_CR18","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0020-0190(97)00183-X","volume":"64","author":"P. Gupta","year":"1997","unstructured":"P. Gupta, R. Janardan, and M. Smid: A technique for adding range restrictions to generalized searching problems, Inform. Process. Lett.\n                           64 (1997), 263\u2013269.","journal-title":"Inform. Process. Lett."},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF02574383","volume":"12","author":"D. Halperin","year":"1994","unstructured":"D. Halperin and M. Sharir: New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Discrete Comput. Geom.\n                           12 (1994), 313\u2013326.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S. Hart","year":"1986","unstructured":"S. Hart and M. Sharir: Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica\n                           6 (1986), 151\u2013177.","journal-title":"Combinatorica"},{"key":"28_CR21","first-page":"77","volume":"12","author":"G. O. H. Katona","year":"1977","unstructured":"G. O. H. Katona: On a problem of L. Fejes Toth, Studia Sci. Math. Hungar.\n                           12 (1977), 77\u201380.","journal-title":"Studia Sci. Math. Hungar."},{"key":"28_CR22","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0925-7721(96)00027-2","volume":"8","author":"M. J. Katz","year":"1997","unstructured":"M. J. Katz: 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, Comput. Geom. Theory Appl.\n                           8 (1997), 299\u2013316.","journal-title":"Comput. Geom. Theory Appl."},{"key":"28_CR23","first-page":"89","volume":"44","author":"M. D. Kovalev","year":"1988","unstructured":"M. D. Kovalev: A property of convex sets and its application (Russian), Mat. Zametki\n                           44 (1988), 89\u201399. English translation: Math. Notes\n                           44 (1988), 537\u2014543.","journal-title":"Mat. Zametki"},{"key":"28_CR24","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K. Kedem","year":"1986","unstructured":"K. Kedem, R. Livne, J. Pach and M. Sharir: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete Comput. Geom.\n                           1 (1986), 59\u201371.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR25","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/BF02187779","volume":"5","author":"K. Kedem","year":"1990","unstructured":"K. Kedem and M. Sharir: An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space, Discrete Comput. Geom.\n                           5 (1990), 43\u201375.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR26","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0925-7721(96)00016-8","volume":"9","author":"M. Kreveld van","year":"1998","unstructured":"M. van Kreveld: On fat partitioning, fat covering and the union size of polygons, Computational Geometry: Theory and Applications\n                           9 (1998), 197\u2013210.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"28_CR27","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF02187867","volume":"2","author":"D. Leven","year":"1987","unstructured":"D. Leven and M. Sharir: Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams, Discrete Comput. Geom.\n                           2 (1987), 9\u201331.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR28","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/PL00009322","volume":"18","author":"L. Lov\u00e1sz","year":"1997","unstructured":"L. Lov\u00e1sz, J. Pach, and M. Szegedy: On Conway\u2019s thrackle conjecture, Discrete Comput. Geom.\n                           18 (1997), 369\u2013376.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR29","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T. Lozano-P\u00e9rez","year":"1979","unstructured":"T. Lozano-P\u00e9rez and M. A. Wesley: An algorithm for planning collision-free paths among polyhedral obstacles, Commun. ACM\n                           22 (1979), 560\u2013570.","journal-title":"Commun. ACM"},{"key":"28_CR30","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1137\/S009753979018330X","volume":"23","author":"J. Matou\u0161sek","year":"1994","unstructured":"J. Matou\u0161sek, J. Pach, M. Sharir, S. Sifrony, and E. Welzl: Fat triangles determine linearly many holes, SIAM Journal of Computing\n                           23 (1994), 154\u2013169.","journal-title":"SIAM Journal of Computing"},{"key":"28_CR31","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0095-8956(71)90042-6","volume":"10","author":"P. McMullen","year":"1971","unstructured":"P. McMullen: On the upper-bound conjecture for convex polytopes, J. Combinatorial Theory, Ser. B\n                           10 (1971), 187\u2013200.","journal-title":"J. Combinatorial Theory, Ser. B"},{"key":"28_CR32","doi-asserted-by":"crossref","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J. Pach","year":"1995","unstructured":"J. Pach and P.K. Agarwal: Combinatorial Geometry, J. Wiley and Sons, New York, 1995."},{"key":"28_CR33","doi-asserted-by":"crossref","unstructured":"J. Pach, I. Safruti, and M. Sharir, The union of congruent cubes in three dimensions, 17th ACM Symposium on Computational Geometry, 2001, accepted.","DOI":"10.1145\/378583.378598"},{"key":"28_CR34","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF02187732","volume":"4","author":"J. Pach","year":"1989","unstructured":"J. Pach and M. Sharir: The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: combinatorial analysis, Discrete Comput. Geom.\n                           4 (1989), 291\u2013309.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR35","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/PL00009424","volume":"21","author":"J. Pach","year":"1999","unstructured":"J. Pach and M. Sharir: On the boundary of the union of planar convex sets, Discrete Comput. Geom.\n                           21 (1999), 321\u2013328.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR36","unstructured":"J. Pach and G. Tardos: On the boundary complexity of the union of fat triangles, Proceedings of 41st Annual Symposium on Foundations of Computer Science, Los Angeles, 2000."},{"key":"28_CR37","doi-asserted-by":"crossref","unstructured":"F. van der Stappen: Motion Planning amidst Fat Obstacles (Ph. D. Thesis, Faculteit Wiskunde & Informatica, Universiteit Utrecht), 1994.","DOI":"10.1145\/177424.177453"},{"key":"28_CR38","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0925-7721(93)90007-S","volume":"3","author":"F. Stappen van der","year":"1993","unstructured":"F. van der Stappen, D. Halperin, and M. Overmars: The complexity of the free space for a robot moving amidst fat obstacles, Computational Geometry: Theory and Applications\n                           3 (1993), 353\u2013373.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"28_CR39","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/cpa.3160360305","volume":"36","author":"J. T. Schwartz","year":"1983","unstructured":"J. T. Schwartz and M. Sharir: On the \u201cpiano movers\u201d problem I,II, Comm. Pure Applied Math.\n                           36 (1983), 345\u2013398 and Adv. Applied Math.\n                           4 (1983), 298\u2014351.","journal-title":"Comm. Pure Applied Math."},{"key":"28_CR40","first-page":"157","volume-title":"Geometric Reasoning","author":"J. T. Schwartz","year":"1989","unstructured":"J. T. Schwartz and M. Sharir: A survey of motion planning and related geometric algorithms, in: Geometric Reasoning (D. Kapur and J. Mundy, eds.), MIT Press, Cambridge, MA, 1989, 157\u2013169."},{"key":"28_CR41","first-page":"391","volume-title":"Handbook of Theoretical Computer Science","author":"J. T. Schwartz","year":"1990","unstructured":"J. T. Schwartz and M. Sharir: Algorithmic motion planning in robotics, in: Handbook of Theoretical Computer Science (J. van Leeuwen, ed.), Elsevier, Amsterdam, 1990, 391\u2013430."},{"key":"28_CR42","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF02574384","volume":"12","author":"M. Sharir","year":"1994","unstructured":"M. Sharir: Almost tight upper bounds for lower envelopes in higher dimensions, Discrete Comput. Geom.\n                           12 (1994), 327\u2013345.","journal-title":"Discrete Comput. Geom."},{"key":"28_CR43","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M. Sharir","year":"1995","unstructured":"M. Sharir and P.K. Agarwel: Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, Cambridge, 1995."},{"key":"28_CR44","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0021-9800(70)80007-2","volume":"8","author":"W. T. Tutte","year":"1970","unstructured":"W. T. Tutte: Toward a theory of crossing numbers, Journal of Combinatorial Theory\n                           8 (1970), 45\u201353.","journal-title":"Journal of Combinatorial Theory"},{"key":"28_CR45","volume-title":"K-admissible collections of Jordan curves and offsets of circular arc figures","author":"S. Whitesides","year":"1990","unstructured":"S. Whitesides and R. Zhao: K-admissible collections of Jordan curves and offsets of circular arc figures, Technical Report SOCS 90.08, McGill University, Montreal, 1990."},{"key":"28_CR46","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF02187894","volume":"3","author":"A. Wiernik","year":"1988","unstructured":"A. Wiernik and M. Sharir: Planar realizations of nonlinear Davenport-Schinzel sequences by segment, Discrete Comput. Geom.\n                           3 (1988, 15\u201347.","journal-title":"Discrete Comput. Geom."}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-47738-1_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T11:01:39Z","timestamp":1558263699000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-47738-1_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540423065","9783540477389"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/3-540-47738-1_28","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"20 September 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}