{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T02:56:10Z","timestamp":1781232970432,"version":"3.54.1"},"reference-count":39,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T00:00:00Z","timestamp":1781136000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This work concerns the harmonization of geospatial data to improve linkages between place-based characteristics and health outcomes. Such data are typically available as geographic layers, each representing a distinct attribute (e.g., income or distance to a clinic). Since layers are typically constructed independently, their boundaries tend to be spatially incongruent, which can create inconsistencies and introduce bias. This motivates developing algorithmic approaches for aligning such layers while aiming to preserve spatial integrity. This paper formalizes the problem of aligning k collections of m spatial supports over n spatial units in a d-dimensional Euclidean space such that maximum distortion to any collection is minimized. In the above setting, k is the number of layers; n is an indivisible population unit (e.g., census tract); m denotes supports, which are larger regions aggregating a set of contiguous units in order to capture broader regional patterns or enhance statistical stability; and d=2. It is shown that: (1) the one-dimensional case is solvable in time polynomial in k, m, and n; (2) the two-dimensional case is NP-hard for two collections of two supports each; and (3) a heuristic can be provided for aligning a set of collections in the two-dimensional case, which is of practical importance.<\/jats:p>","DOI":"10.3390\/a19060475","type":"journal-article","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T01:52:08Z","timestamp":1781229128000},"page":"475","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Spatial Alignment Problem"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5253-144X","authenticated-orcid":false,"given":"Armin R.","family":"Mikler","sequence":"first","affiliation":[{"name":"Department of Computer Science, Georgia State University, Atlanta, GA 30302, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3869-4023","authenticated-orcid":false,"given":"Chetan","family":"Tiwari","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Georgia State University, Atlanta, GA 30302, USA"},{"name":"Department of Geosciences, Georgia State University, Atlanta, GA 30302, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4329-0234","authenticated-orcid":false,"given":"Murray","family":"Patterson","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Georgia State University, Atlanta, GA 30302, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,6,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1186\/1476-072X-3-28","article-title":"Current practices in spatial analysis of cancer data: Data characteristics and data sources for geographic studies of cancer","volume":"3","author":"Boscoe","year":"2004","journal-title":"Int. J. Health Geogr."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1093\/jncimonographs\/lgae015","article-title":"Landscape analysis of environmental data sources for linkage with SEER cancer patients database","volume":"2024","author":"Tatalovich","year":"2024","journal-title":"JNCI Monogr."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"995","DOI":"10.1289\/ehp.6736","article-title":"Health and environment information systems for exposure and disease mapping, and risk assessment","volume":"112","author":"Jarup","year":"2004","journal-title":"Environ. Health Perspect."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2109","DOI":"10.1093\/aje\/kwac155","article-title":"Developing geographic areas for cancer reporting using automated zone design","volume":"191","author":"Tatalovich","year":"2022","journal-title":"Am. J. Epidemiol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2544","DOI":"10.1002\/cncr.32052","article-title":"GIScience and cancer: State of the art and trends for cancer surveillance and epidemiology","volume":"125","author":"Sahar","year":"2019","journal-title":"Cancer"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1186\/s12963-018-0164-6","article-title":"The relevance of spatial aggregation level and of applied methods in the analysis of geographical distribution of cancer mortality in mainland Portugal (2009\u20132013)","volume":"16","author":"Roquette","year":"2018","journal-title":"Popul. Health Metr."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1289\/ehp.02110s2161","article-title":"Mapping environmental injustices: Pitfalls and potential of geographic information systems in assessing environmental health and equity","volume":"110","author":"Maantay","year":"2002","journal-title":"Environ. Health Perspect."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1158\/1055-9965.EPI-23-1237","article-title":"Geospatial Science for the Environmental Epidemiology of Cancer in the Exposome Era","volume":"33","author":"VoPham","year":"2024","journal-title":"Cancer Epidemiol. Biomark. Prev."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1194","DOI":"10.1109\/TSMCA.2012.2183360","article-title":"A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement","volume":"42","author":"Jimenez","year":"2012","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1949","DOI":"10.1068\/a3497","article-title":"The application of zone-design methodology in the 2001 UK Census","volume":"33","author":"Martin","year":"2001","journal-title":"Environ. Plan. A"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1080\/713811750","article-title":"Extending the automated zoning procedure to reconcile incompatible zoning systems","volume":"17","author":"Martin","year":"2003","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_12","unstructured":"Herring, J.R. (2011). OpenGIS Implementation Standard for Geographic Information\u2013Simple Feature Access\u2013Part 1: Common Architecture, Open Geospatial Consortium. Version 1.2.1, OGC 06-103r4."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2203","DOI":"10.1002\/1097-0258(20000915\/30)19:17\/18<2203::AID-SIM564>3.0.CO;2-U","article-title":"A classification of disease mapping methods","volume":"19","author":"Bithell","year":"2000","journal-title":"Stat. Med."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1146\/annurev.publhealth.24.012902.140843","article-title":"Public Health, GIS, and Spatial Analytic Tools","volume":"24","author":"Rushton","year":"2003","journal-title":"Annu. Rev. Public Health"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1080\/00045608.2012.659940","article-title":"Five essential properties of disease maps","volume":"102","author":"Beyer","year":"2012","journal-title":"Ann. Assoc. Am. Geogr."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1002\/(SICI)1097-0258(19960415)15:7\/9<717::AID-SIM243>3.0.CO;2-0","article-title":"Exploratory spatial analysis of birth defect rates in an urban population","volume":"15","author":"Rushton","year":"1996","journal-title":"Stat. Med."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"671","DOI":"10.2307\/2532003","article-title":"Empirical Bayes estimates of age-standardized relative risks for use in disease mapping","volume":"43","author":"Clayton","year":"1987","journal-title":"Biometrics"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"100593","DOI":"10.1016\/j.spasta.2022.100593","article-title":"Bayesian disease mapping: Past, present, and future","volume":"50","author":"MacNab","year":"2022","journal-title":"Spat. Stat."},{"key":"ref_19","unstructured":"Tiwari, C., and Rushton, G. (2005). Using spatially adaptive filters to map late stage colorectal cancer incidence in Iowa. Developments in Spatial Data Handling: 11 th International Symposium on Spatial Data Handling, Springer."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1080\/13658810902950625","article-title":"Selection of bandwidth type and adjustment side in kernel density estimation over inhomogeneous backgrounds","volume":"24","author":"Shi","year":"2010","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1109\/36.79427","article-title":"Head-banging: Robust smoothing in the plane","volume":"29","author":"Hansen","year":"1991","journal-title":"IEEE Trans. Geosci. Remote Sens."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3201","DOI":"10.1002\/(SICI)1097-0258(19991215)18:23<3201::AID-SIM310>3.0.CO;2-U","article-title":"Application of a weighted head-banging algorithm to mortality data maps","volume":"18","author":"Mungiole","year":"1999","journal-title":"Stat. Med."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2399","DOI":"10.1002\/1097-0258(20000915\/30)19:17\/18<2399::AID-SIM577>3.0.CO;2-R","article-title":"Evaluation of spatial filters to create smoothed maps of health data","volume":"19","author":"Talbot","year":"2000","journal-title":"Stat. Med."},{"key":"ref_24","unstructured":"Korf, R.E. (2009, January 11\u201317). Multi-way number partitioning. Proceedings of the the 21st International Joint Conferences on Artificial Intelligence (IJCAI), Pasadena, CA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","article-title":"Bounds on Multiprocessing Timing Anomalies","volume":"17","author":"Graham","year":"1969","journal-title":"SIAM J. Appl. Math."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Coffman, E.G., and Sethi, R. (1976, January 29\u201331). A generalized bound on LPT sequencing. Proceedings of the 1976 ACM SIGMETRICS Conference on Computer Performance Modeling Measurement and Evaluation, Cambridge, MA, USA.","DOI":"10.1145\/800200.806205"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations, Springer.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref_29","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intracability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Compnany."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Cygan, M. (2013, January 26\u201329). Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2013.61"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M., and Yu, H. (2014). Approximating the k-Set Packing Problem by Local Improvements. International Symposium on Combinatorial Optimization, Springer.","DOI":"10.1007\/978-3-319-09174-7_35"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0165-4896(88)90047-9","article-title":"Equitable distribution of indivisible objects","volume":"16","author":"Demko","year":"1988","journal-title":"Math. Soc. Sci."},{"key":"ref_33","unstructured":"Bouveret, S., Endriss, U., and Lang, J. (2010, January 16\u201320). Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods. Proceedings of the 2010 Conference on ECAI 2010: 19th European Conference on Artificial Intelligence, Lisbon, Portugal."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Aziz, H., Rauchecker, G., Schryen, G., and Walsh, T. (2017). Algorithms for Max-Min Share Fair Allocation of Indivisible Chores. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI Press.","DOI":"10.1609\/aaai.v31i1.10582"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/3381525","article-title":"Approximation Algorithms for Maximin Fair Division","volume":"8","author":"Barman","year":"2020","journal-title":"ACM Trans. Econ. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/s10458-015-9287-3","article-title":"Characterizing conflicts in fair division of indivisible goods using a scale of criteria","volume":"30","author":"Bouveret","year":"2016","journal-title":"Proc. Auton. Agents Multi-Agent Syst."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., and Saberi, A. (2004, January 17\u201320). On approximately fair allocations of indivisible goods. Proceedings of the 5th ACM Conference on Electronic Commerce, New York, NY, USA.","DOI":"10.1145\/988772.988792"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/2728732.2728738","article-title":"Spliddit: Unleashing fair division algorithms","volume":"13","author":"Goldman","year":"2015","journal-title":"SIGecom Exch."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Procaccia, A.D., and Wang, J. (2014, January 8\u201312). Fair enough: Guaranteeing approximate maximin shares. Proceedings of the Fifteenth ACM Conference on Economics and Computation, Palo Alto, CA, USA.","DOI":"10.1145\/2600057.2602835"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/6\/475\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T01:56:49Z","timestamp":1781229409000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/6\/475"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,11]]},"references-count":39,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2026,6]]}},"alternative-id":["a19060475"],"URL":"https:\/\/doi.org\/10.3390\/a19060475","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,11]]}}}