{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:24:41Z","timestamp":1760441081642},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,10,24]],"date-time":"2012-10-24T00:00:00Z","timestamp":1351036800000},"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,4]]},"DOI":"10.1007\/s00453-012-9704-9","type":"journal-article","created":{"date-parts":[[2012,10,23]],"date-time":"2012-10-23T15:48:53Z","timestamp":1351007333000},"page":"805-834","source":"Crossref","is-referenced-by-count":3,"title":["Computing the Map of Geometric Minimal Cuts"],"prefix":"10.1007","volume":"68","author":[{"given":"Jinhui","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evanthia","family":"Papadopoulou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,10,24]]},"reference":[{"key":"9704_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/PL00009296","volume":"17","author":"M. Abellanas","year":"1997","unstructured":"Abellanas, M., Hernandez, G., Klein, R., Neumann-Lara, V., Urrutia, J.: A combinatorial property of convex sets. Discrete Comput. Geom. 17, 307\u2013318 (1997)","journal-title":"Discrete Comput. Geom."},{"key":"9704_CR2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF02523236","volume":"17","author":"F. Dehne","year":"1997","unstructured":"Dehne, F., Klein, R.: The Big Sweep: on the power of the wavefront approach to Voronoi diagrams. Algorithmica 17, 19\u201332 (1997)","journal-title":"Algorithmica"},{"key":"9704_CR3","first-page":"497","volume-title":"Proc. 2006 International Conference on Parallel Processing","author":"F. Dehne","year":"2006","unstructured":"Dehne, F., Maheshwari, A., Taylor, R.: A coarse grained parallel algorithm for Hausdorff Voronoi diagrams. In: Proc. 2006 International Conference on Parallel Processing, pp. 497\u2013504 (2006)"},{"key":"9704_CR4","first-page":"109","volume-title":"Proceedings of the 18th annual ACM symposium on Theory of computing","author":"J.R. Driscoll","year":"1986","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D., Tarjan, R.: Making data structures persistent. In: Proceedings of the 18th annual ACM symposium on Theory of computing, pp. 109\u2013121 (1986)"},{"key":"9704_CR5","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/BF02187733","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.J., Sharir, M.: The upper envelope of piecewise linear functions: algorithms and applications. Discrete Comput. Geom. 4, 311\u2013336 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"9704_CR6","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D. Eppstein","year":"1997","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification\u2014a technique for speeding up dynamic graph algorithms. J. ACM 44(5), 669\u2013696 (1997)","journal-title":"J. ACM"},{"issue":"4","key":"9704_CR7","doi-asserted-by":"crossref","first-page":"878","DOI":"10.1109\/JSSC.1985.1052404","volume":"20","author":"A. Ferris-Prabhu","year":"1985","unstructured":"Ferris-Prabhu, A.: Defect size variations and their effect on the critical area of VLSI devices. IEEE J. Solid-State Circuits 20(4), 878\u2013880 (1985)","journal-title":"IEEE J. Solid-State Circuits"},{"key":"9704_CR8","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S. Fortune","year":"1987","unstructured":"Fortune, S.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153\u2013174 (1987)","journal-title":"Algorithmica"},{"issue":"4","key":"9704_CR9","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14(4), 781\u2013798 (1985)","journal-title":"SIAM J. Comput."},{"key":"9704_CR10","first-page":"519","volume-title":"Proceedings of the 27th Annual ACM Symposium on Theory of Computing","author":"M.R. Henzinger","year":"1995","unstructured":"Henzinger, M.R., King, V.: Randomized dynamic graph algorithms with polylogarithmic time per operation. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 519\u2013527 (1995)"},{"key":"9704_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-52055-4","volume-title":"Concrete and Abstract Voronoi Diagrams","author":"R. Klein","year":"1989","unstructured":"Klein, R.: Concrete and Abstract Voronoi Diagrams. Lecture Notes in Computer Science, vol. 400. Springer, Berlin (1989)"},{"issue":"9","key":"9704_CR12","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1016\/j.comgeo.2009.03.002","volume":"42","author":"R. Klein","year":"2009","unstructured":"Klein, R., Langetepe, E., Nilforoushan, Z.: Abstract Voronoi diagrams revisited. Comput. Geom. 42(9), 885\u2013902 (2009)","journal-title":"Comput. Geom."},{"key":"9704_CR13","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0925-7721(93)90033-3","volume":"3","author":"R. Klein","year":"1993","unstructured":"Klein, R., Mehlhorn, K., Meiser, S.: Randomized incremental construction of abstract Voronoi diagram. Comput. Geom. 3, 157\u2013184 (1993)","journal-title":"Comput. Geom."},{"key":"9704_CR14","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<369::AID-RSA5>3.0.CO;2-X","volume":"11","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Thorup, M.: Sampling to provide or to bound: with applications to fully dynamic graph algorithms. Random Struct. Algorithms 11, 363\u2013379 (1997)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"9704_CR15","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"9704_CR16","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01840386","volume":"5","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Dynamic fractional cascading. Algorithmica 5, 215\u2013241 (1990)","journal-title":"Algorithmica"},{"issue":"4","key":"9704_CR17","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1109\/69.234779","volume":"5","author":"Y. Nakamura","year":"1993","unstructured":"Nakamura, Y., ABE, S., Ohsawa, Y., Sakauchi, M.: MD-tree: a balanced hierarchical data structure for multi-dimensional data with highly efficient dynamic characteristics. IEEE Trans. Knowl. Data Eng. 5(4), 682\u2013694 (1993)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"5","key":"9704_CR18","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1109\/43.920683","volume":"20","author":"E. Papadopoulou","year":"2001","unstructured":"Papadopoulou, E.: Critical area computation for missing material defects in VLSI circuits. IEEE Trans. Comput.-Aided Des. 20(5), 583\u2013597 (2001)","journal-title":"IEEE Trans. Comput.-Aided Des."},{"key":"9704_CR19","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/s00453-004-1095-0","volume":"40","author":"E. Papadopoulou","year":"2004","unstructured":"Papadopoulou, E.: The Hausdorff Voronoi diagram of point clusters in the plane. Algorithmica 40, 63\u201382 (2004)","journal-title":"Algorithmica"},{"key":"9704_CR20","series-title":"LNCS","first-page":"716","volume-title":"ISAAC\u201907","author":"E. Papadopoulou","year":"2007","unstructured":"Papadopoulou, E.: Higher order Voronoi diagrams of segments for VLSI critical area extraction. In: ISAAC\u201907. LNCS, vol. 4835, pp. 716\u2013727 (2007)"},{"issue":"5","key":"9704_CR21","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1109\/TCAD.2010.2100550","volume":"30","author":"E. Papadopoulou","year":"2011","unstructured":"Papadopoulou, E.: Net-Aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 30(5), 704\u2013717 (2011)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"9704_CR22","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1142\/S0218195901000626","volume":"11","author":"E. Papadopoulou","year":"2001","unstructured":"Papadopoulou, E., Lee, D.T.: The L \u221e Voronoi diagram of segments and VLSI applications. Int. J. Comput. Geom. Appl. 11, 503\u2013528 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"9704_CR23","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1109\/43.752929","volume":"18","author":"E. Papadopoulou","year":"1999","unstructured":"Papadopoulou, E., Lee, D.T.: Critical area computation via Voronoi diagrams. IEEE Trans. Comput.-Aided Des. 18(4), 463\u2013474 (1999)","journal-title":"IEEE Trans. Comput.-Aided Des."},{"issue":"6","key":"9704_CR24","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1142\/S0218195904001536","volume":"14","author":"E. Papadopoulou","year":"2004","unstructured":"Papadopoulou, E., Lee, D.T.: The Hausdorff Voronoi diagram of polygonal objects: a divide and conquer approach. Int. J. Comput. Geom. Appl. 14(6), 421\u2013452 (2004)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9704_CR25","volume-title":"IEEE-CS Proceedings of Int. Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011","author":"E. Papadopoulou","year":"2011","unstructured":"Papadopoulou, E., Xu, J.: The L \u221e Hausdorff Voronoi diagram revisited. In: IEEE-CS Proceedings of Int. Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011 (2011)"},{"key":"9704_CR26","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1145\/335305.335345","volume-title":"STOC\u201900","author":"M. Thorup","year":"2000","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: STOC\u201900, pp. 343\u2013350 (2000)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9704-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9704-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9704-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T10:20:52Z","timestamp":1687774852000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9704-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,24]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["9704"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9704-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,24]]}}}