{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T21:53:09Z","timestamp":1718920389247},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"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,3]]},"DOI":"10.1007\/bf02523191","type":"journal-article","created":{"date-parts":[[2006,11,7]],"date-time":"2006-11-07T23:41:28Z","timestamp":1162942888000},"page":"245-265","source":"Crossref","is-referenced-by-count":16,"title":["Decomposing the boundary of a nonconvex polyhedron"],"prefix":"10.1007","volume":"17","author":[{"given":"B.","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L.","family":"Palios","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02523191_CR1","doi-asserted-by":"crossref","unstructured":"E. Arkin, R. Connelly, and J. S. B. Mitchell, On Monotone Paths Among Obstacles, with Applications to Planning Assemblies,Proc. 5th Annual ACM Symposium on Computational Geometry (1989) pp. 334\u2013343.","DOI":"10.1145\/73833.73870"},{"key":"BF02523191_CR2","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1137\/0221025","volume":"21","author":"C. L. Bajaj","year":"1992","unstructured":"C. L. Bajaj and T. K. Dey, Convex Decompositions of Polyhedra and Robustness,SIAM Journal on Computing 21 (1992), 339\u2013364.","journal-title":"SIAM Journal on Computing"},{"key":"BF02523191_CR3","series-title":"AFIPS Conference Proceedings","first-page":"589","volume-title":"Proc. 1975National Computer Conference","author":"B. G. Baumgart","year":"1975","unstructured":"B. G. Baumgart, A Polyhedron Representation for Computer Vision,Proc. 1975National Computer Conference, AFIPS Conference Proceedings, Vol. 44 (1975), AFIPS Press, Montvale, NJ, pp. 589\u2013596."},{"key":"BF02523191_CR4","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1137\/0213031","volume":"13","author":"B. Chazelle","year":"1984","unstructured":"B. Chazelle, Convex Partitions of Polyhedra: A Lower Bound and Worst Cast Optimal Algorithm,SIAM Journal on Computing 13 (1984), 488\u2013507.","journal-title":"SIAM Journal on Computing"},{"key":"BF02523191_CR5","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/BF02187747","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle and L. J. Guibas, Visibility and Intersection Problems in Plane Geometry,Discrete and Computational Geometry 4 (1989), 551\u2013581.","journal-title":"Discrete and Computational Geometry"},{"key":"BF02523191_CR6","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/BF02187807","volume":"5","author":"B. Chazelle","year":"1990","unstructured":"B. Chazelle and L. Palios, Triangulating a Nonconvex Polytope,Discrete and Computational Geometry 5 (1990), 505\u2013526.","journal-title":"Discrete and Computational Geometry"},{"key":"BF02523191_CR7","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L. J. Guibas","year":"1987","unstructured":"L. J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan, Linear Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons,Algorithmica 2 (1987), 209\u2013233.","journal-title":"Algorithmica"},{"key":"BF02523191_CR8","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1145\/282918.282923","volume":"4","author":"L. J. Guibas","year":"1985","unstructured":"L. J. Guibas and J. Stolfi, Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams,ACM Transactions on Graphics 4 (1985), 75\u2013123.","journal-title":"ACM Transactions on Graphics"},{"key":"BF02523191_CR9","series-title":"Lecture Notes on Computer Science","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/3-540-12689-9_105","volume-title":"Fast Triangulation of a Simple Polygon","author":"S. Hertel","year":"1983","unstructured":"S. Hertel and K. Mehlhorn,Fast Triangulation of a Simple Polygon, Lecture Notes on Computer Science, Vol. 158 (1983), Springer-Verlag, Berlin, pp. 207\u2013218."},{"key":"BF02523191_CR10","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. G. Kirkpatrick","year":"1983","unstructured":"D. G. Kirkpatrick, Optimal Search in Planar Subdivisions,SIAM Journal on Computing 12 (1983), 28\u201335.","journal-title":"SIAM Journal on Computing"},{"key":"BF02523191_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BFb0012784","volume-title":"The Power of Non-Rectilinear Holes","author":"A. Lingas","year":"1982","unstructured":"A. Lingas,The Power of Non-Rectilinear Holes, Lecture Notes in Computer Science, Vol. 140 (1982), Springer-Verlag, Berlin, pp. 369\u2013383."},{"key":"BF02523191_CR12","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-3975(78)90051-8","volume":"7","author":"D. E. Muller","year":"1978","unstructured":"D. E. Muller and F. P. Preparata, Finding the Intersection of two Convex Polyhedra,Theoretical Computer Science 7 (1978), 217\u2013236.","journal-title":"Theoretical Computer Science"},{"key":"BF02523191_CR13","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O'Rourke","year":"1987","unstructured":"J. O'Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, Oxford (1987)."},{"key":"BF02523191_CR14","unstructured":"J. Ruppert and R. Seidel, On the Difficulty of Tetrahedralizing 3-Dimensional Non-Convex Polyhedra,Proc. 5th Annual ACM Symposium on Computational Geometry (1989), pp. 380\u2013392."},{"key":"BF02523191_CR15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0734-189X(86)90127-1","volume":"35","author":"S. Suri","year":"1986","unstructured":"S. Suri, A Linear Time Algorithm for Minimum Link Paths Inside a Simple Polygon,Computer Vision, Graphics, and Image Processing 35 (1986), 99\u2013110.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"BF02523191_CR16","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02187729","volume":"4","author":"G. T. Toussaint","year":"1989","unstructured":"G. T. Toussaint, On Separating Two Simple Polygons by a Single Translation,Discrete and Computational Geometry 4 (1989), 265\u2013278.","journal-title":"Discrete and Computational Geometry"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523191.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523191\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:39:41Z","timestamp":1558283981000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["BF02523191"],"URL":"https:\/\/doi.org\/10.1007\/bf02523191","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}