{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T06:33:24Z","timestamp":1784010804208,"version":"3.55.0"},"publisher-location":"Cham","reference-count":76,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319919072","type":"print"},{"value":"9783319919089","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[[2019]]},"DOI":"10.1007\/978-3-319-91908-9_5","type":"book-chapter","created":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T05:05:00Z","timestamp":1570165500000},"page":"66-84","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Geometric Optimization Revisited"],"prefix":"10.1007","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Esther","family":"Ezra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kyle","family":"Fox","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,10,5]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Hansen, T.D., Williams, V.V., Williams, R.: Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In: Proceedings of the 48th Annual ACM Symposium on Theory Computing, pp. 375\u2013388 (2016)","DOI":"10.1145\/2897518.2897653"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: Proceedings of the 54th IEEE Annual Symposium on Foundations of Computer Science, pp. 400\u2013409 (2013)","DOI":"10.1109\/FOCS.2013.50"},{"key":"5_CR3","first-page":"1","volume-title":"Combinatorial and Computational Geometry","author":"PK Agarwal","year":"2005","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Geometricapproximation via coresets. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry, pp. 1\u201330. Cambridge University Press, New York (2005)"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1137\/130920526","volume":"43","author":"PK Agarwal","year":"2014","unstructured":"Agarwal, P.K., Avraham, R.B., Kaplan, H., Sharir, M.: Computing the discrete fr\u00e9chet distance in subquadratic time. SIAM J. Comput. 43, 429\u2013449 (2014)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"5_CR5","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1137\/S0097539795295936","volume":"29","author":"PK Agarwal","year":"1999","unstructured":"Agarwal, P.K., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM J. Comput. 29(3), 912\u2013953 (1999)","journal-title":"SIAM J. Comput."},{"key":"5_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-02085-8_22","volume-title":"Distributed Computing in Sensor Systems","author":"PK Agarwal","year":"2009","unstructured":"Agarwal, P.K., Ezra, E., Ganjugunte, S.K.: Efficient sensor placement for surveillance problems. In: Krishnamachari, B., Suri, S., Heinzelman, W., Mitra, U. (eds.) DCOSS 2009. LNCS, vol. 5516, pp. 301\u2013314. Springer, Heidelberg (2009). \n                      https:\/\/doi.org\/10.1007\/978-3-642-02085-8_22"},{"issue":"1\u20132","key":"5_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-011-9517-2","volume":"63","author":"PK Agarwal","year":"2012","unstructured":"Agarwal, P.K., Ezra, E., Sharir, M.: Near-linear approximation algorithms for geometric hitting sets. Algorithmica 63(1\u20132), 1\u201325 (2012)","journal-title":"Algorithmica"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/978-3-662-48971-0_45","volume-title":"Algorithms and Computation","author":"Pankaj K. Agarwal","year":"2015","unstructured":"Agarwal, P.K., Fox, K., Nath, A., Sidiropoulos, A., Wang, Y.: Computing the Gromov-Hausdorff distance for metric trees. In: Proceedings of 26th International Symposium on Algorithms and Computation, pp. 529\u2013540 (2015)"},{"key":"5_CR9","unstructured":"Agarwal, P.K., Fox, K., Pan, J., Ying, R.: Approximating dynamic time warping and edit distance for a pair of point sequences. In: 32nd International Symposium on Computational Geometry, pp. 6:1\u20136:16 (2016)"},{"key":"5_CR10","unstructured":"Agarwal, P.K., Fox, K., Panigrahi, D., Varadarajan, K., Xiao, A.: Efficient algorithms for the geometric transportation problem. In: 33rd International Symposium on Computational Geometry (2017, to appear)"},{"issue":"2","key":"5_CR11","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.comgeo.2005.12.001","volume":"34","author":"PK Agarwal","year":"2006","unstructured":"Agarwal, P.K., Mustafa, N.H.: Independent set of intersection graphs of convex objects in 2D. Comput. Geom. 34(2), 83\u201395 (2006)","journal-title":"Comput. Geom."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Pan, J.: Near-linear algorithms for geometric hitting sets and set covers. In: Proceedings of the 30th Annual Symposium on Computational Geometry, pp. 271\u2013280 (2014)","DOI":"10.1145\/2582112.2582152"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Sharathkumar, R.: Approximation algorithms for bipartite matchingwith metric and geometric costs. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 555\u2013564 (2014)","DOI":"10.1145\/2591796.2591844"},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/BFb0015247","volume-title":"Computer Science Today","author":"PK Agarwal","year":"1995","unstructured":"Agarwal, P.K., Sharir, M.: Algorithmic techniques for geometric optimization. In: van Leeuwen, J. (ed.) Computer Science Today. LNCS, vol. 1000, pp. 234\u2013253. Springer, Heidelberg (1995). \n                      https:\/\/doi.org\/10.1007\/BFb0015247"},{"issue":"4","key":"5_CR15","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1145\/299917.299918","volume":"30","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., Sharir, M.: Efficient algorithms for geometric optimization. ACM Comput. Surv. 30(4), 412\u2013458 (1998)","journal-title":"ACM Comput. Surv."},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Varadarajan, K.R.: A near-linear constant-factor approximation for Euclidean bipartite matching? In: Proceedings of the 20th Annual Symposium on Computational Geometry, pp. 247\u2013252 (2004)","DOI":"10.1145\/997817.997856"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Alt, H., Guibas, L.J.: Discrete geometric shapes: matching, interpolation, and approximation. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 121 \u2013 153. North-Holland, Amsterdam (2000)","DOI":"10.1016\/B978-044482537-7\/50004-8"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Andoni, A., Nikolov, A., Onak, K., Yaroslavtsev, G.: Parallel algorithms for geometric graph problems. In: Proceedings of the 46th ACM Symposium on Theory of Computing, pp. 574\u2013583 (2014)","DOI":"10.1145\/2591796.2591805"},{"issue":"2","key":"5_CR19","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/120891241","volume":"43","author":"B Aronov","year":"2014","unstructured":"Aronov, B., de Berg, M., Ezra, E., Sharir, M.: Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput. 43(2), 543\u2013572 (2014)","journal-title":"SIAM J. Comput."},{"key":"5_CR20","doi-asserted-by":"crossref","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size \n                      \n                        \n                      \n                      $$\\varepsilon $$\n                    -nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39, 3248\u20133282 (2010)","journal-title":"SIAM J. Comput."},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/11841036_8","volume-title":"Algorithms \u2013 ESA 2006","author":"B Aronov","year":"2006","unstructured":"Aronov, B., Har-Peled, S., Knauer, C., Wang, Y., Wenk, C.: Fr\u00e9chet distance for curves, revisited. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 52\u201363. Springer, Heidelberg (2006). \n                      https:\/\/doi.org\/10.1007\/11841036_8"},{"issue":"5","key":"5_CR22","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"5_CR23","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s10107-003-0438-y","volume":"97","author":"S Arora","year":"2003","unstructured":"Arora, S.: Approximation schemes for NP-hard geometric optimization problems: a survey. Math. Program. 97(1\u20132), 43\u201369 (2003)","journal-title":"Math. Program."},{"issue":"5","key":"5_CR24","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1007\/BF01190848","volume":"13","author":"DS Atkinson","year":"1995","unstructured":"Atkinson, D.S., Vaidya, P.M.: Using geometry to solve the transportation problem in the plane. Algorithmica 13(5), 442\u2013461 (1995)","journal-title":"Algorithmica"},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1109\/34.121791","volume":"14","author":"PJ Besl","year":"1992","unstructured":"Besl, P.J., McKay, N.D.: A method for registration of 3-D shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14, 239\u2013256 (1992)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"5_CR26","unstructured":"Bonnet, \u00c9., Miltzow, T.: An approximation algorithm for the art gallery problem. CoRR abs\/1607.05527 (2016). \n                      http:\/\/arxiv.org\/abs\/1607.05527"},{"key":"5_CR27","unstructured":"Bonnet, \u00c9., Miltzow, T.: Parameterized hardness of art gallery problems. In: 24th Annual European Symposium on Algorithms, vol. 57, pp. 19:1\u201319:17 (2016)"},{"issue":"2","key":"5_CR28","first-page":"46","volume":"7","author":"K Bringmann","year":"2016","unstructured":"Bringmann, K., Mulzer, W.: Approximability of the discrete fr\u00e9chet distance. J. Comput. Geom. 7(2), 46\u201376 (2016)","journal-title":"J. Comput. Geom."},{"issue":"5","key":"5_CR29","doi-asserted-by":"publisher","first-page":"1812","DOI":"10.1137\/050639296","volume":"28","author":"AM Bronstein","year":"2006","unstructured":"Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Efficient computation of isometry-invariant distances between surfaces. SIAM J. Sci. Comput. 28(5), 1812\u20131836 (2006)","journal-title":"SIAM J. Sci. Comput."},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 892\u2013901 (2009)","DOI":"10.1137\/1.9781611973068.97"},{"issue":"2","key":"5_CR31","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"TM Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46(2), 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"issue":"2","key":"5_CR32","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"50","author":"TM Chan","year":"2008","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in \n                      \n                        \n                      \n                      $$O(n^3 \/ \\log n)$$\n                     time. Algorithmica 50(2), 236\u2013243 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"5_CR33","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.comgeo.2012.04.001","volume":"47","author":"TM Chan","year":"2014","unstructured":"Chan, T.M., Grant, E.: Exact algorithms and apx-hardness results for geometric packing and covering problems. Comput. Geom. 47(2), 112\u2013124 (2014)","journal-title":"Comput. Geom."},{"key":"5_CR34","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Grant, E., K\u00f6nemann, J., Sharpe, M.: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In: Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms, pp. 1576\u20131585 (2012)","DOI":"10.1137\/1.9781611973099.125"},{"key":"5_CR35","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"TM Chan","year":"2012","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Disc. Comput. Geom. 48, 373\u2013392 (2012)","journal-title":"Disc. Comput. Geom."},{"issue":"1","key":"5_CR36","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/2390176.2390185","volume":"9","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Clarkson, K.L., Har-Peled, S.: On the set multicover problem in geometric settings. ACM Trans. Algorithms 9(1), 9:1\u20139:17 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"5_CR37","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s00454-007-1328-5","volume":"37","author":"O Cheong","year":"2007","unstructured":"Cheong, O., Efrat, A., Har-Peled, S.: Finding a guard that sees most and a shop that sells most. Disc. Comput. Geom. 37(4), 545\u2013563 (2007)","journal-title":"Disc. Comput. Geom."},{"key":"5_CR38","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Ene, A.: On approximating maximum independent set of rectangles. In: Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, pp. 820\u2013829 (2016)","DOI":"10.1109\/FOCS.2016.92"},{"issue":"1","key":"5_CR39","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"KL Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. Disc. Comput. Geom. 37(1), 43\u201358 (2007)","journal-title":"Disc. Comput. Geom."},{"key":"5_CR40","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 624\u2013633 (2014)","DOI":"10.1145\/2591796.2591884"},{"issue":"1","key":"5_CR41","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00454-012-9402-z","volume":"48","author":"A Driemel","year":"2012","unstructured":"Driemel, A., Har-Peled, S., Wenk, C.: Approximating the Fr\u00e9chet distance for realistic curves in near linear time. Disc. Comput. Geom. 48(1), 94\u2013127 (2012)","journal-title":"Disc. Comput. Geom."},{"issue":"1","key":"5_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-001-0016-8","volume":"31","author":"A Efrat","year":"2001","unstructured":"Efrat, A., Itai, A., Katz, M.J.: Geometry helps in bottleneck matching and related problems. Algorithmica 31(1), 1\u201328 (2001)","journal-title":"Algorithmica"},{"issue":"1","key":"5_CR43","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00453-001-0040-8","volume":"31","author":"S Eidenbenz","year":"2001","unstructured":"Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31(1), 79\u2013113 (2001)","journal-title":"Algorithmica"},{"issue":"2","key":"5_CR44","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/j.ipl.2005.03.010","volume":"95","author":"G Even","year":"2005","unstructured":"Even, G., Rawitz, D., Shahar, S.: Hitting sets when the VC-dimension is small. Inf. Process. Lett. 95(2), 358\u2013362 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"5_CR45","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1137\/S089548010240415X","volume":"18","author":"U Feige","year":"2004","unstructured":"Feige, U.: Approximating maximum clique by removing subgraphs. SIAM J. Discret. Math. 18(2), 219\u2013225 (2004)","journal-title":"SIAM J. Discret. Math."},{"key":"5_CR46","doi-asserted-by":"crossref","unstructured":"Fox, J., Pach, J.: Computing the independence number of intersection graphs. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1161\u20131165 (2011)","DOI":"10.1137\/1.9781611973082.87"},{"issue":"3","key":"5_CR47","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"5_CR48","unstructured":"Gold, O., Sharir, M.: Dynamic time warping and geometric edit distance: Breaking the quadratic barrier. CoRR abs\/1607.05994 (2016)"},{"key":"5_CR49","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/173","volume-title":"Geometric Approximation Algorithms","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. American Mathematical Society, Boston (2011)"},{"key":"5_CR50","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: Quasi-polynomial time approximation scheme for sparse subsets of polygons. In: Proceedings of the 30th Annual Symposium on Computational Geometry, pp. 120\u2013129 (2014)","DOI":"10.1145\/2582112.2582157"},{"key":"5_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/978-3-662-48350-3_60","volume-title":"Algorithms - ESA 2015","author":"S Har-Peled","year":"2015","unstructured":"Har-Peled, S., Quanrud, K.: Approximation algorithms for polynomial-expansion and low-density graphs. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 717\u2013728. Springer, Heidelberg (2015). \n                      https:\/\/doi.org\/10.1007\/978-3-662-48350-3_60"},{"key":"5_CR52","volume-title":"Approximation Algorithms for NP-Hard Problems","year":"1997","unstructured":"Hochbaum, D.S. (ed.): Approximation Algorithms for NP-Hard Problems. PWS Publishing Co., Boston (1997)"},{"key":"5_CR53","unstructured":"Indyk, P.: A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 39\u201342 (2007)"},{"issue":"6","key":"5_CR54","doi-asserted-by":"publisher","first-page":"1681","DOI":"10.1111\/j.1467-8659.2011.01884.x","volume":"30","author":"O Kaick van","year":"2011","unstructured":"van Kaick, O., Zhang, H., Hamarneh, G., Cohen-Or, D.: A survey on shape correspondence. Comput. Graph. Forum 30(6), 1681\u20131707 (2011)","journal-title":"Comput. Graph. Forum"},{"key":"5_CR55","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495\u20132504 (2017)","DOI":"10.1137\/1.9781611974782.165"},{"key":"5_CR56","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, Boston (1972). \n                      https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"key":"5_CR57","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A.: Path finding methods for linear programming: solving linear programs in \u00d5(vrank) iterations and faster algorithms for maximum flow. In: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, pp. 424\u2013433 (2014)","DOI":"10.1109\/FOCS.2014.52"},{"key":"5_CR58","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0220026","volume":"20","author":"O Marcotte","year":"1991","unstructured":"Marcotte, O., Suri, S.: Fast matching algorithms for points on a polygon. SIAM J. Comput. 20, 405\u2013422 (1991)","journal-title":"SIAM J. Comput."},{"key":"5_CR59","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Springer, New York (2002). \n                      https:\/\/doi.org\/10.1007\/978-1-4613-0039-7"},{"issue":"3","key":"5_CR60","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s10208-004-0145-y","volume":"5","author":"F M\u00e9moli","year":"2005","unstructured":"M\u00e9moli, F., Sapiro, G.: A theoretical and computational framework for isometry invariant recognition of point cloud data. Found. Comput. Math. 5(3), 313\u2013347 (2005)","journal-title":"Found. Comput. Math."},{"issue":"4","key":"5_CR61","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"5_CR62","doi-asserted-by":"crossref","unstructured":"Mustafa, N.H., Raman, R., Ray, S.: Settling the APX-hardness status for geometric set cover. In: Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, pp. 541\u2013550 (2014)","DOI":"10.1109\/FOCS.2014.64"},{"issue":"4","key":"5_CR63","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"NH Mustafa","year":"2010","unstructured":"Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Disc. Comput. Geom. 44(4), 883\u2013895 (2010)","journal-title":"Disc. Comput. Geom."},{"issue":"2","key":"5_CR64","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1287\/opre.41.2.338","volume":"41","author":"JB Orlin","year":"1993","unstructured":"Orlin, J.B.: A faster strongly polynomial minimum cost flow algorithm. Oper. Res. 41(2), 338\u2013350 (1993)","journal-title":"Oper. Res."},{"key":"5_CR65","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1090\/S0894-0347-2012-00759-0","volume":"26","author":"J Pach","year":"2013","unstructured":"Pach, J., Tardos, G.: Tight lower bounds for the size of epsilon-nets. J. Am. Math. Soc. 26, 645\u2013658 (2013)","journal-title":"J. Am. Math. Soc."},{"key":"5_CR66","unstructured":"Phillips, J.M.: Coresets and sketches. CoRR abs\/1601.00617 (2016)"},{"issue":"4","key":"5_CR67","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1007\/s00454-017-9889-4","volume":"57","author":"F Schmiedl","year":"2017","unstructured":"Schmiedl, F.: Computational aspects of the Gromov-Hausdorff distance and its application in non-rigid shape matching. Disc. Comput. Geom. 57(4), 854\u2013880 (2017)","journal-title":"Disc. Comput. Geom."},{"key":"5_CR68","doi-asserted-by":"crossref","unstructured":"Sharathkumar, R., Agarwal, P.K.: Algorithms for the transportation problem in geometric settings. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 306\u2013317 (2012)","DOI":"10.1137\/1.9781611973099.29"},{"key":"5_CR69","doi-asserted-by":"crossref","unstructured":"Sharathkumar, R., Agarwal, P.K.: A near-linear time \n                      \n                        \n                      \n                      $$\\varepsilon $$\n                    -approximation algorithm for geometric bipartite matching. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pp. 385\u2013394 (2012)","DOI":"10.1145\/2213977.2214014"},{"key":"5_CR70","doi-asserted-by":"crossref","unstructured":"Urrutia, J.: Art gallery and illumination problems. In: Handbook of Computational Geometry, pp. 973\u20131027. North-Holland (2000)","DOI":"10.1016\/B978-044482537-7\/50023-1"},{"issue":"6","key":"5_CR71","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/0218080","volume":"18","author":"PM Vaidya","year":"1989","unstructured":"Vaidya, P.M.: Geometry helps in matching. SIAM J. Comput. 18(6), 1201\u20131225 (1989)","journal-title":"SIAM J. Comput."},{"key":"5_CR72","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.R.: Weighted geometric set cover via quasi-uniform sampling. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 641\u2013648 (2010)","DOI":"10.1145\/1806689.1806777"},{"key":"5_CR73","unstructured":"Varadarajan, K.R., Agarwal, P.K.: Approximation algorithms for bipartite and non-bipartite matching in the plane. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 805\u2013814 (1999)"},{"key":"5_CR74","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001). \n                      https:\/\/doi.org\/10.1007\/978-3-662-04565-7"},{"key":"5_CR75","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71050-9","volume-title":"Optimal Transport: Old and New","author":"C Villani","year":"2008","unstructured":"Villani, C.: Optimal Transport: Old and New, vol. 338. Springer, Heidelberg (2008). \n                      https:\/\/doi.org\/10.1007\/978-3-540-71050-9"},{"key":"5_CR76","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Lecture Notes in Computer Science","Computing and Software Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-91908-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T20:07:58Z","timestamp":1570306078000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-91908-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783319919072","9783319919089"],"references-count":76,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-91908-9_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"5 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}