{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:15:11Z","timestamp":1725887711216},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319591070"},{"type":"electronic","value":"9783319591087"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59108-7_10","type":"book-chapter","created":{"date-parts":[[2017,5,16]],"date-time":"2017-05-16T04:43:06Z","timestamp":1494909786000},"page":"117-131","source":"Crossref","is-referenced-by-count":2,"title":["Algorithms for Stable Matching and Clustering in a Grid"],"prefix":"10.1007","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nil","family":"Mamano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,17]]},"reference":[{"issue":"7","key":"10_CR1","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1016\/0010-4485(89)90125-5","volume":"21","author":"V Akman","year":"1989","unstructured":"Akman, V., Franklin, W.R., Kankanhalli, M., Narayanaswami, C.: Geometric computing and uniform grid technique. Comput.-Aid. Des. 21(7), 410\u2013420 (1989)","journal-title":"Comput.-Aid. Des."},{"issue":"1","key":"10_CR2","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0925-7721(00)00015-8","volume":"17","author":"EM Arkin","year":"2000","unstructured":"Arkin, E.M., Fekete, S.P., Mitchell, J.S.B.: Approximation algorithms for lawn mowing and milling. Comput. Geom. 17(1), 25\u201350 (2000)","journal-title":"Comput. Geom."},{"issue":"3","key":"10_CR3","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi diagrams\u2013a survey of a fundamental geometric data structure. ACM Comput. Surv. 23(3), 345\u2013405 (1991)","journal-title":"ACM Comput. Surv."},{"key":"10_CR4","unstructured":"Benz\u00e9cri, J.P.: Construction d\u2019une classification ascendante hi\u00e9rarchique par la recherche en cha\u00eene des voisins r\u00e9ciproques. Les Cahiers de l\u2019Analyse des Donn\u00e9es 7(2), 209\u2013218 (1982). http:\/\/www.numdam.org\/item?id=CAD_1982__7_2_209_0"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Biedl, T., Bl\u00e4sius, T., Niedermann, B., N\u00f6llenburg, M., Prutkin, R., Rutter, I.: Using ILP\/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings. In: Wismath, S., Wolff, A. (eds.) 21st International Symposium on Graph Drawing (GD), pp. 460\u2013471 (2013)","DOI":"10.1007\/978-3-319-03841-4_40"},{"issue":"2","key":"10_CR6","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/PL00009460","volume":"22","author":"KF B\u00f6hringer","year":"1999","unstructured":"B\u00f6hringer, K.F., Donald, R.B., Halperin, D.: On the area bisectors of a polygon. Discrete Comput. Geom. 22(2), 269\u2013285 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. J. ACM 57(3), 16: 1\u201316: 15 (2010)","DOI":"10.1145\/1706591.1706596"},{"issue":"2","key":"10_CR8","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1137\/07068669X","volume":"39","author":"TM Chan","year":"2009","unstructured":"Chan, T.M., Patrascu, M.: Transdichotomous results in computational geometry, i: point location in sublogarithmic time. SIAM J. Comput. 39(2), 703\u2013729 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10_CR9","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF01758750","volume":"7","author":"S Chandran","year":"1992","unstructured":"Chandran, S., Kim, S.K., Mount, D.M.: Parallel computational geometry of rectangles. Algorithmica 7(1), 25\u201349 (1992)","journal-title":"Algorithmica"},{"issue":"1","key":"10_CR10","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0925-7721(98)00016-9","volume":"11","author":"M Chrobak","year":"1998","unstructured":"Chrobak, M., Nakano, S.: Minimum-width grid drawings of plane graphs. Comput. Geom. 11(1), 29\u201354 (1998)","journal-title":"Comput. Geom."},{"issue":"3","key":"10_CR11","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/s00454-009-9166-2","volume":"42","author":"J Chun","year":"2009","unstructured":"Chun, J., Korman, M., N\u00f6llenburg, M., Tokuyama, T.: Consistent digital rays. Discrete Comput. Geom. 42(3), 359\u2013378 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"10_CR12","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms, 2nd edn. McGraw-Hill Higher Education, Boston (2001)","edition":"2"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"De Floriani, L., Puppo, E., Magillo, P.: Applications of computational geometry to geographic information systems. In: Handbook of Computational Geometry, pp. 333\u2013388 (1999)","DOI":"10.1016\/B978-044482537-7\/50008-5"},{"issue":"1","key":"10_CR14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H Fraysseix De","year":"1990","unstructured":"De Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41\u201351 (1990)","journal-title":"Combinatorica"},{"issue":"3","key":"10_CR15","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/BF01407955","volume":"19","author":"F Dehne","year":"1990","unstructured":"Dehne, F., Pham, Q.T., Stojmenovi\u0107, I.: Optimal visibility algorithms for binary images on the hypercube. Int. J. Parallel Programm. 19(3), 213\u2013224 (1990)","journal-title":"Int. J. Parallel Programm."},{"issue":"1","key":"10_CR16","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02574030","volume":"13","author":"D Eppstein","year":"1995","unstructured":"Eppstein, D.: Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete Comput. Geom. 13(1), 111\u2013122 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"10_CR17","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1109\/38.210490","volume":"13","author":"TP Fang","year":"1993","unstructured":"Fang, T.P., Piegl, L.A.: Delaunay triangulation using a uniform grid. IEEE Comput. Graph. Appl. 13(3), 36\u201347 (1993)","journal-title":"IEEE Comput. Graph. Appl."},{"issue":"1","key":"10_CR18","doi-asserted-by":"crossref","first-page":"9","DOI":"10.2307\/2312726","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Monthly 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Monthly"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Greene, D.H., Yao, F.F.: Finite-resolution computational geometry. In: 27th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 143\u2013152 (1986)","DOI":"10.1109\/SFCS.1986.19"},{"key":"10_CR20","volume-title":"Multiple View Geometry in Computer Vision","author":"R Hartley","year":"2003","unstructured":"Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, New York (2003)"},{"issue":"4","key":"10_CR21","doi-asserted-by":"crossref","first-page":"1241","DOI":"10.1214\/009117906000000098","volume":"34","author":"C Hoffman","year":"2006","unstructured":"Hoffman, C., Holroyd, A.E., Peres, Y.: A stable marriage of Poisson and Lebesgue. Ann. Probab. 34(4), 1241\u20131272 (2006)","journal-title":"Ann. Probab."},{"issue":"3","key":"10_CR22","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1145\/331499.331504","volume":"31","author":"AK Jain","year":"1999","unstructured":"Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: a review. ACM Comput. Surv. 31(3), 264\u2013323 (1999)","journal-title":"ACM Comput. Surv."},{"key":"10_CR23","unstructured":"Juan, J.: Programme de classification hi\u00e9rarchique par l\u2019algorithme de la recherche en cha\u00eene des voisins r\u00e9ciproques. Les Cahiers de l\u2019Analyse des Donn\u00e9es 7(2), 219\u2013225 (1982). http:\/\/www.numdam.org\/item?id=CAD_1982__7_2_219_0"},{"issue":"7","key":"10_CR24","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1109\/TPAMI.2002.1017616","volume":"24","author":"T Kanungo","year":"2002","unstructured":"Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: An efficient $$k$$ -means clustering algorithm: analysis and implementation. IEEE Trans. Pattern Anal. Mach. Intell. 24(7), 881\u2013892 (2002)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"10_CR25","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. Electronic preprint arxiv:1604.03654 (2016)","DOI":"10.1137\/1.9781611974782.165"},{"key":"10_CR26","unstructured":"Keil, J.M.: Computational geometry on an integer grid. Ph.D. thesis, University of British Columbia (1980)"},{"key":"10_CR27","volume-title":"The Art of Computer Programming Sorting and Searching","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming Sorting and Searching. Pearson Education, Reading (1998)"},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"Overmars, M.H.: Computational geometry on a grid an overview. In: Earnshaw R.A. (eds.) Theoretical Foundations of Computer Graphics and CAD. NATO ASI Series (Series F: Computer and Systems Sciences), vol. 40, pp. 167\u2013184. Springer, Heidelberg (1988)","DOI":"10.1007\/978-3-642-83539-1_5"},{"issue":"2","key":"10_CR29","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0196-6774(88)90041-7","volume":"9","author":"MH Overmars","year":"1988","unstructured":"Overmars, M.H.: Efficient data structures for range searching on a grid. J. Algorithms 9(2), 254\u2013275 (1988)","journal-title":"J. Algorithms"},{"issue":"3","key":"10_CR30","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0925-7721(98)00003-0","volume":"10","author":"MS Rahman","year":"1998","unstructured":"Rahman, M.S., Nakano, S., Nishizeki, T.: Rectangular grid drawings of plane graphs. Comput. Geom. 10(3), 203\u2013220 (1998)","journal-title":"Comput. Geom."},{"issue":"9\u201310","key":"10_CR31","doi-asserted-by":"crossref","first-page":"1468","DOI":"10.1016\/j.mcm.2008.05.041","volume":"48","author":"F Ricca","year":"2008","unstructured":"Ricca, F., Scozzari, A., Simeone, B.: Weighted Voronoi region algorithms for political districting. Math. Comput. Modell. 48(9\u201310), 1468\u20131477 (2008)","journal-title":"Math. Comput. Modell."},{"key":"10_CR32","unstructured":"Solbrig, M.: Mathematical Aspects of Gerrymandering. Master\u2019s thesis, University of Washington (2013). https:\/\/digital.lib.washington.edu\/researchworks\/handle\/1773\/24334"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Image Analysis"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59108-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T14:06:37Z","timestamp":1569333997000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59108-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319591070","9783319591087"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59108-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}