FF-SA: Fragmentation-free spatial allocation

Yiqun Xie, Shashi Shekhar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


Given a grid G containing a set of orthogonal grid cells and a list L of choices on each grid cell (e.g., land use), the fragmentation-free spatial allocation (FF-SA) aims to find a tile-partition of G and choice assignment on each tile so that the overall benefit is maximized under a cost constraint as well as spatial geometric constraints (e.g., minimum tile area, shape). The spatial constraints are necessary to avoid fragmentation and maintain practicality of the spatial allocation result. The application domains include agricultural landscape design (a.k.a., Geodesign), urban land-use planning, building floor zoning, etc. The problem is computationally challenging as an APX-hard problem. Existing spatial allocation techniques either do not consider spatial constraints during space-tiling or are very limited in enumeration space. We propose a Hierarchical Fragmentation Elimination (HFE) algorithm to address the fragmentation issue and significantly increase the enumeration space of tiling schemes. The new algorithm was evaluated through a detailed case study on spatial allocation of agricultural lands in mid-western US, and the results showed improved solution quality compared to the existing work.

Original languageEnglish (US)
Title of host publicationAdvances in Spatial and Temporal Databases - 15th International Symposium, SSTD 2017, Proceedings
EditorsWei-Shinn Ku, Agnes Voisard, Haiquan Chen, Chang-Tien Lu, Siva Ravada, Matthias Renz, Yan Huang, Michael Gertz, Liang Tang, Chengyang Zhang, Erik Hoel, Xiaofang Zhou
PublisherSpringer- Verlag
Number of pages20
ISBN (Print)9783319643663
StatePublished - Jan 1 2017
Event15th International Symposium on Spatial and Temporal Databases, SSTD 2017 - Arlington, United States
Duration: Aug 21 2017Aug 23 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10411 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other15th International Symposium on Spatial and Temporal Databases, SSTD 2017
Country/TerritoryUnited States


Dive into the research topics of 'FF-SA: Fragmentation-free spatial allocation'. Together they form a unique fingerprint.

Cite this