{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:24:49Z","timestamp":1760441089340},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,8,11]],"date-time":"2012-08-11T00:00:00Z","timestamp":1344643200000},"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":[[2014,2]]},"DOI":"10.1007\/s00453-012-9679-6","type":"journal-article","created":{"date-parts":[[2012,8,10]],"date-time":"2012-08-10T17:33:02Z","timestamp":1344619982000},"page":"448-482","source":"Crossref","is-referenced-by-count":4,"title":["Relative Convex Hulls in Semi-Dynamic Arrangements"],"prefix":"10.1007","volume":"68","author":[{"given":"Mashhood","family":"Ishaque","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,8,11]]},"reference":[{"issue":"3","key":"9679_CR1","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.comgeo.2003.11.001","volume":"27","author":"J. Basch","year":"2004","unstructured":"Basch, J., Erickson, J., Guibas, L.J., Hershberger, J., Zhang, L.: Kinetic collision detection between two simple polygons. Comput. Geom. 27(3), 211\u2013235 (2004)","journal-title":"Comput. Geom."},{"issue":"9","key":"9679_CR2","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"C-28","author":"J.L. Bentley","year":"1979","unstructured":"Bentley, J.L., Ottmann, T.A.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C-28(9), 643\u2013647 (1979)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"9679_CR3","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s11786-010-0042-5","volume":"4","author":"E. Berberich","year":"2010","unstructured":"Berberich, E., Fogel, E., Halperin, D., Mehlhorn, K., Wein, R.: Arrangements on parametric surfaces I: general framework and infrastructure. Math. Comput. Sci. 4(1), 45\u201366 (2010)","journal-title":"Math. Comput. Sci."},{"issue":"6","key":"9679_CR4","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1142\/S0218195911003822","volume":"21","author":"M.G. Borgelt","year":"2011","unstructured":"Borgelt, M.G., van Kreveld, M.J., Luo, J.: Geodesic disks and clustering in a simple polygon. Int. J. Comput. Geom. Appl. 21(6), 595\u2013608 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"9679_CR5","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s00454-006-1287-2","volume":"37","author":"P. Bose","year":"2007","unstructured":"Bose, P., Demaine, E.D., Hurtado, F., Iacono, J., Langerman, S., Morin, P.: Geodesic ham-sandwich cuts. Discrete Comput. Geom. 37(3), 325\u2013339 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"9679_CR6","first-page":"617","volume-title":"Proc. 43rd Sympos on Foundations of Comp. Sci. (FOCS)","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: Proc. 43rd Sympos on Foundations of Comp. Sci. (FOCS), pp. 617\u2013626. IEEE Press, New York (2002)"},{"issue":"1","key":"9679_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/363647.363652","volume":"48","author":"T.M. Chan","year":"2001","unstructured":"Chan, T.M.: Dynamic planar convex hull operations in near-logarithmic amortized time. J. ACM 48(1), 1\u201312 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"9679_CR8","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/TIT.1985.1057060","volume":"IT-31","author":"B. Chazelle","year":"1985","unstructured":"Chazelle, B.: On the convex layers of a planar set. IEEE Trans. Inf. Theory IT-31(4), 509\u2013517 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9679_CR9","doi-asserted-by":"crossref","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 12, 54\u201368 (1994)","journal-title":"Algorithmica"},{"key":"9679_CR10","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01758854","volume":"8","author":"B. Chazelle","year":"1992","unstructured":"Chazelle, B., Sharir, M., Welzl, E.: Quasi-optimal upper bounds for simplex range searching and new zone theorems. Algorithmica 8, 407\u2013429 (1992)","journal-title":"Algorithmica"},{"key":"9679_CR11","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1137\/S0097539792224516","volume":"25","author":"Y.-J. Chiang","year":"1996","unstructured":"Chiang, Y.-J., Preparata, F.P., Tamassia, R.: A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. SIAM J. Comput. 25, 207\u2013233 (1996)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9679_CR12","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1142\/S0218195997000181","volume":"7","author":"J. Choi","year":"1997","unstructured":"Choi, J., Sellen, J., Yap, C.K.: Approximate Euclidean shortest paths in 3-space. Int. J. Comput. Geom. Appl. 7(4), 271\u2013295 (1997)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9679_CR13","unstructured":"Choi, J.S.: Geodesic problems in high dimensions. Ph.D. Thesis, Courant Institute, New York University, New York (1995)"},{"issue":"2","key":"9679_CR14","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s00454-010-9262-3","volume":"44","author":"R. Connelly","year":"2010","unstructured":"Connelly, R., Demaine, E.D., Demaine, M.L., Fekete, S., Langerman, S., Mitchell, J.S.B., Rib\u00f3, A., Rote, G.: Locked and unlocked chains of planar shapes. Discrete Comput. Geom. 44(2), 439\u2013462 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9679_CR15","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s00454-003-0006-7","volume":"30","author":"R. Connelly","year":"2003","unstructured":"Connelly, R., Demaine, E.D., Rote, G.: Straightening polygonal arcs and convexifying polygonal cycles. Discrete Comput. Geom. 30(2), 205\u2013239 (2003)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9679_CR16","volume":"7","author":"A.F. Cook","year":"2010","unstructured":"Cook, A.F., Wenk, C.: Geodesic Fr\u00e9chet distance inside a simple polygon. ACM Trans. Algorithms 7(1), 9 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9679_CR17","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H. Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.: Topologically sweeping an arrangement. J. Comput. Syst. Sci. 38(1), 165\u2013194 (1989). J. Comput. Syst. Sci. 42, 249\u2013251 (1991) (corrigendum)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"9679_CR18","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0166-218X(00)00232-8","volume":"109","author":"S. Felsner","year":"2001","unstructured":"Felsner, S., Weil, H.: Sweeps, arrangements and signotopes. Discrete Appl. Math. 109(1\u20132), 67\u201394 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9679_CR19","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1109\/TRO.2009.2013493","volume":"25","author":"A. Ganguli","year":"2009","unstructured":"Ganguli, A., Cortes, J., Bullo, F.: Multirobot rendezvous with visibility sensors in nonconvex environments. IEEE Trans. Robot. 25(2), 340\u2013352 (2009)","journal-title":"IEEE Trans. Robot."},{"key":"9679_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511543340","volume-title":"Visibility Algorithms in the Plane","author":"S. Ghosh","year":"2007","unstructured":"Ghosh, S.: Visibility Algorithms in the Plane. Cambridge University Press, New York (2007)"},{"issue":"3","key":"9679_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1541885.1541889","volume":"5","author":"Y. Giyora","year":"2009","unstructured":"Giyora, Y., Kaplan, H.: Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Trans. Algorithms 5(3), 1\u201351 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"9679_CR22","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1006\/jagm.1995.0797","volume":"23","author":"M.T. Goodrich","year":"1997","unstructured":"Goodrich, M.T., Tamassia, R.: Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations. J. Algorithms 23, 51\u201373 (1997)","journal-title":"J. Algorithms"},{"key":"9679_CR23","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0022-0000(89)90041-X","volume":"39","author":"L. Guibas","year":"1989","unstructured":"Guibas, L., Hershberger, J.: Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci. 39, 126\u2013152 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9679_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s004540010017","volume":"24","author":"L.J. Guibas","year":"2000","unstructured":"Guibas, L.J., Hershberger, J., Suri, S.: Morphing simple polygons. Discrete Comput. Geom. 24(1), 1\u201334 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"9679_CR25","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01994880","volume":"32","author":"J. Hershberger","year":"1992","unstructured":"Hershberger, J., Suri, S.: Applications of a semi-dynamic convex hull algorithm. BIT Numer. Math. 32, 249\u2013267 (1992)","journal-title":"BIT Numer. Math."},{"issue":"1","key":"9679_CR26","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. 26(1), 47\u201368 (2003)","journal-title":"Comput. Geom."},{"key":"9679_CR27","first-page":"101","volume-title":"Proc. Canadian Conf. Comput. Geom","author":"M. Hoffmann","year":"2006","unstructured":"Hoffmann, M., T\u00f3th, C.D.: Spanning trees across axis-parallel segments. In: Proc. Canadian Conf. Comput. Geom, pp. 101\u2013104 (2006)"},{"issue":"3","key":"9679_CR28","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1007\/s00454-009-9145-7","volume":"41","author":"H.N. Iben","year":"2009","unstructured":"Iben, H.N., O\u2019Brien, J.F., Demaine, E.D.: Refolding planar polygons. Discrete Comput. Geom. 41(3), 444\u2013460 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"9679_CR29","doi-asserted-by":"crossref","unstructured":"Ishaque, M., Speckmann, B., T\u00f3th, C.D.: Shooting permanent rays among disjoint polygons in the plane. SIAM J. Comput. (2012, to appear). A preliminary version appeared in Proc. 25th Sympos. on Comput. Geom., pp.\u00a051\u201360. ACM, New York (2009)","DOI":"10.1145\/1542362.1542372"},{"key":"9679_CR30","unstructured":"Jacob, R.: Dynamic planar convex hull. Ph.D. Thesis, University of Aarhus, Aarhus, Denmark (2002)"},{"key":"9679_CR31","first-page":"179","volume-title":"Proc. 18th Sympos. on Comput. Geom","author":"D.G. Kirkpatrick","year":"2002","unstructured":"Kirkpatrick, D.G., Speckmann, B.: Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons. In: Proc. 18th Sympos. on Comput. Geom, pp. 179\u2013188. ACM, New York (2002)"},{"issue":"3","key":"9679_CR32","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/s00454-007-9025-y","volume":"40","author":"D.W. Krumme","year":"2008","unstructured":"Krumme, D.W., Rafalin, E., Souvaine, D.L., T\u00f3th, C.D.: Tight bounds for connecting sites across barriers. Discrete Comput. Geom. 40(3), 377\u2013394 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"9679_CR33","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"D.T. Lee","year":"1984","unstructured":"Lee, D.T., Preparata, F.P.: Euclidean shortest paths in the presence of rectilinear barriers. Networks 14, 393\u2013410 (1984)","journal-title":"Networks"},{"key":"9679_CR34","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Efficient partition trees. Discrete Comput. Geom. 8, 315\u2013334 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"9679_CR35","volume-title":"Handbook of Computational Geometry","author":"J.S.B. Mitchell","year":"2000","unstructured":"Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Handbook of Computational Geometry. Elsevier, Amsterdam (2000)"},{"key":"9679_CR36","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M.H. Overmars","year":"1981","unstructured":"Overmars, M.H., van Leeuwen, J.: Maintenance of configurations in the plane. J. Comput. Syst. Sci. 23, 166\u2013204 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"9679_CR37","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1145\/359131.359132","volume":"22","author":"F.P. Preparata","year":"1979","unstructured":"Preparata, F.P.: An optimal real-time algorithm for planar convex hulls. Commun. ACM 22, 402\u2013405 (1979)","journal-title":"Commun. ACM"},{"issue":"17","key":"9679_CR38","doi-asserted-by":"crossref","first-page":"3276","DOI":"10.1016\/j.dam.2008.06.019","volume":"156","author":"E. Rafalin","year":"2008","unstructured":"Rafalin, E., Souvaine, D.L.: Topological sweep of the complete graph. Discrete Appl. Math. 156(17), 3276\u20133290 (2008)","journal-title":"Discrete Appl. Math."},{"key":"9679_CR39","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1007\/978-3-642-55566-4_33","volume-title":"Discrete and Computational Geometry\u2013The Goodman-Pollack Festschrift","author":"G. Rote","year":"2003","unstructured":"Rote, G., Santos, F., Streinu, I.: Expansive motions and the polytope of pointed pseudo-triangulations. In: Discrete and Computational Geometry\u2013The Goodman-Pollack Festschrift. Algorithms and Combinatorics, vol. 25, pp. 699\u2013736. Springer, Berlin (2003)"},{"key":"9679_CR40","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1109\/TC.1972.5008948","volume":"C-21","author":"J. Sklansky","year":"1972","unstructured":"Sklansky, J., Chazin, R.L., Hansen, B.J.: Minimum perimeter polygons of digitized silhouettes. IEEE Trans. Comput. C-21, 260\u2013268 (1972)","journal-title":"IEEE Trans. Comput."},{"key":"9679_CR41","first-page":"354","volume-title":"Proc. 5th Sympos. on Comput. Geom","author":"J. Snoeyink","year":"1989","unstructured":"Snoeyink, J., Hershberger, J.: Sweeping arrangements of curves. In: Proc. 5th Sympos. on Comput. Geom, pp. 354\u2013363. ACM, New York (1989)"},{"issue":"4","key":"9679_CR42","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1007\/s00454-005-1184-0","volume":"34","author":"I. Streinu","year":"2005","unstructured":"Streinu, I.: Pseudo-triangulations, rigidity and motion planning. Discrete Comput. Geom. 34(4), 587\u2013635 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"9679_CR43","first-page":"853","volume-title":"Proc. 3rd European Signal Processing Conf. on Signal Processing III: Theories and Applications","author":"G. Toussaint","year":"1986","unstructured":"Toussaint, G.: An optimal algorithm for computing the relative convex hull of a set of points in a polygon. In: Proc. 3rd European Signal Processing Conf. on Signal Processing III: Theories and Applications, pp. 853\u2013856. North-Holland, Amsterdam (1986)"},{"issue":"2","key":"9679_CR44","first-page":"9","volume":"3","author":"G. Toussaint","year":"1989","unstructured":"Toussaint, G.: Computing geodesic properties inside a simple polygon. Rev. Intell. Artif. 3(2), 9\u201342 (1989)","journal-title":"Rev. Intell. Artif."},{"issue":"1","key":"9679_CR45","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02187729","volume":"4","author":"G. Toussaint","year":"1989","unstructured":"Toussaint, G.: On separating two simple polygons by a single translation. Discrete Comput. Geom. 4(1), 265\u2013278 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9679_CR46","series-title":"LNCS","first-page":"532","volume-title":"Proc. 11th European Sympos. on Algorithms","author":"N. Wolpert","year":"2003","unstructured":"Wolpert, N.: Jacobi curves: computing the exact topology of arrangements of non-singular algebraic curves. In: Proc. 11th European Sympos. on Algorithms. LNCS, vol. 2832, pp. 532\u2013543. Springer, Berlin (2003)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9679-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9679-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9679-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,26]],"date-time":"2022-01-26T06:22:48Z","timestamp":1643178168000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9679-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,11]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9679"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9679-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,11]]}}}