{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:58Z","timestamp":1725559018736},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_38","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T13:27:29Z","timestamp":1279027649000},"page":"442-454","source":"Crossref","is-referenced-by-count":0,"title":["Pointed Binary Encompassing Trees"],"prefix":"10.1007","author":[{"given":"Michael","family":"Hoffmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bettina","family":"Speckmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"38_CR1","unstructured":"Agarwal, P.K., Basch, J., Guibas, L.J., Hershberger, J., Zhang, L.: Deformable free space tilings for kinetic collision detection. In: Proc. 4th WAFR, pp. 83\u201396 (2001)"},{"key":"38_CR2","unstructured":"Aichholzer, O., Hoffmann, M., Speckmann, B.: Degree bounds for constrained pseudo-triangulations. In: Proc. 15th CCCG, pp. 155\u2013158 (2003)"},{"key":"38_CR3","unstructured":"Aichholzer, O., Huemer, C., Krasser, H.: Triangulations without pointed spanning trees. In: Abstracts of 20th European Workshop Comput. Geom. (2004)"},{"key":"38_CR4","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/S0196-6774(03)00090-7","volume":"49","author":"S. Bespamyatnikh","year":"2003","unstructured":"Bespamyatnikh, S.: Computing homotopic shortest paths in the plane. J. Algorithms\u00a049, 284\u2013303 (2003)","journal-title":"J. Algorithms"},{"key":"38_CR5","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s00454-001-0042-y","volume":"26","author":"P. Bose","year":"2001","unstructured":"Bose, P., Houle, M.E., Toussaint, G.T.: Every set of disjoint line segments admits a binary tree. Discrete Comput Geom.\u00a026, 387\u2013410 (2001)","journal-title":"Discrete Comput Geom."},{"key":"38_CR6","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1006\/jagm.1995.1028","volume":"19","author":"P. Bose","year":"1995","unstructured":"Bose, P., Toussaint, G.T.: Growing a tree from its branches. J. Algorithms\u00a019, 86\u2013103 (1995)","journal-title":"J. Algorithms"},{"key":"38_CR7","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/BF01377183","volume":"12","author":"B. Chazelle","year":"1994","unstructured":"Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L.J., Hershberger, J., Sharir, M., Snoeyink, J.: Ray shooting in polygons using geodesic triangulations. Algorithmica\u00a012, 54\u201368 (1994)","journal-title":"Algorithmica"},{"key":"38_CR8","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1137\/0221057","volume":"21","author":"S.-W. Cheng","year":"1992","unstructured":"Cheng, S.-W., Janardan, R.: New results on dynamic planar point location. SIAM J. Comput.\u00a021, 972\u2013999 (1992)","journal-title":"SIAM J. Comput."},{"key":"38_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/3-540-45749-6_38","volume-title":"Algorithms - ESA 2002","author":"A. Efrat","year":"2002","unstructured":"Efrat, A., Kobourov, S., Lubiw, A.: Computing homotopic shortest paths efficiently. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 411\u2013423. Springer, Heidelberg (2002)"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/jagm.1995.0797","volume":"23","author":"M. Goodrich","year":"1997","unstructured":"Goodrich, M., Tamassia, R.: Dynamic ray shooting and shortest paths in planar subdivision via balanced geodesic triangulations. J. Algorithms\u00a023, 51\u201373 (1997)","journal-title":"J. Algorithms"},{"key":"38_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0020-0190(03)00349-1","volume":"87","author":"M. Hoffmann","year":"2003","unstructured":"Hoffmann, M., T\u00f3th, C.D.: Alternating paths through disjoint line segments. Inform. Proc. Letts.\u00a087, 287\u2013294 (2003)","journal-title":"Inform. Proc. Letts."},{"key":"38_CR12","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0925-7721(02)00172-4","volume":"26","author":"M. Hoffmann","year":"2003","unstructured":"Hoffmann, M., T\u00f3th, C.D.: Segment endpoint visibility graphs are Hamiltonian. Comput. Geom. Theory Appl.\u00a026, 47\u201368 (2003)","journal-title":"Comput. Geom. Theory Appl."},{"key":"38_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0925-7721(02)00125-6","volume":"25","author":"L. Kettner","year":"2003","unstructured":"Kettner, L., Kirkpatrick, D., Mantler, A., Snoeyink, J., Speckmann, B., Takeuchi, F.: Tight degree bounds for pseudo-triangulations of points. Comput. Geom. Theory Appl.\u00a025, 1\u201312 (2003)","journal-title":"Comput. Geom. Theory Appl."},{"key":"38_CR14","first-page":"179","volume-title":"Proc. 18th Sympos. Comput. Geom.","author":"D. Kirkpatrick","year":"2002","unstructured":"Kirkpatrick, D., Speckmann, B.: Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons. In: Proc. 18th Sympos. Comput. Geom., pp. 179\u2013188. ACM, New York (2002)"},{"key":"38_CR15","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0925-7721(95)00016-X","volume":"6","author":"M. Pocchiola","year":"1996","unstructured":"Pocchiola, M., Vegter, G.: Minimal tangent visibility graphs. Comput. Geom.Theory Appl.\u00a06, 303\u2013314 (1996)","journal-title":"Comput. Geom.Theory Appl."},{"key":"38_CR16","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF02712876","volume":"16","author":"M. Pocchiola","year":"1996","unstructured":"Pocchiola, M., Vegter, G.: Topologically sweeping visibility complexes via pseudo-triangulations. Discrete Comput. Geom.\u00a016, 419\u2013453 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"38_CR17","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1137\/0218075","volume":"18","author":"D. Rappaport","year":"1989","unstructured":"Rappaport, D.: Computing simple circuits from a set of line segments is NPcomplete. SIAM J. Comput.\u00a018, 1128\u20131139 (1989)","journal-title":"SIAM J. Comput."},{"key":"38_CR18","first-page":"109","volume-title":"Proc. 14th SODA","author":"B. Speckmann","year":"2003","unstructured":"Speckmann, B., T\u00f3th, C.D.: Allocating vertex \u03c0-guards in simple polygons via pseudo-triangulations. In: Proc. 14th SODA, pp. 109\u2013118. ACM Press, New York (2003)"},{"key":"38_CR19","first-page":"443","volume-title":"Proc. 41st FOCS","author":"I. Streinu","year":"2000","unstructured":"Streinu, I.: A combinatorial approach to planar non-colliding robot arm motion planning. In: Proc. 41st FOCS, pp. 443\u2013453. IEEE Press, Los Alamitos (2000)"},{"key":"38_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-540-45078-8_34","volume-title":"Algorithms and Data Structures","author":"C..D. T\u00f3th","year":"2003","unstructured":"T\u00f3th, C.D.: Alternating paths along orthogonal segments. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 389\u2013400. Springer, Heidelberg (2003)"},{"key":"38_CR21","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0925-7721(92)90020-S","volume":"2","author":"M. Urabe","year":"1992","unstructured":"Urabe, M., Watanabe, M.: On a counterexample to a conjecture of Mirzaian, Comput. Geom. Theory Appl.\u00a02, 51\u201353 (1992)","journal-title":"Geom. Theory Appl."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T23:27:11Z","timestamp":1619998031000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}