{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:34:17Z","timestamp":1760369657608,"version":"build-2065373602"},"reference-count":49,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T00:00:00Z","timestamp":1603411200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003565","name":"Ministry of Land, Infrastructure and Transport","doi-asserted-by":"publisher","award":["20NSIP-B135746-04"],"award-info":[{"award-number":["20NSIP-B135746-04"]}],"id":[{"id":"10.13039\/501100003565","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Utilizing indoor spaces has become important with the progress of localization and positioning technologies. Covering and partitioning problems play an important role in managing, indexing, and analyzing spatial data. In this paper, we propose a multi-stage framework for indoor space partitioning, each stage of which can be flexibly adjusted according to target applications. One of the main features of our framework is the parameterized constraint, which characterizes the properties and restrictions of unit geometries used for the covering and partitioning tasks formulated as the binary linear programs. It enables us to apply the proposed method to various problems by simply changing the constraint parameter. We present basic constraints that are widely used in many covering and partitioning problems regarding the indoor space applications along with several techniques that simplify the computation process. We apply it to particular applications, device placement and route planning problems, in order to give examples of the use of our framework in the perspective on how to design a constraint and how to use the resulting partitions. We also demonstrate the effectiveness with experimental results compared to baseline methods.<\/jats:p>","DOI":"10.3390\/ijgi9110618","type":"journal-article","created":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T08:59:28Z","timestamp":1603443568000},"page":"618","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Flexible Framework for Covering and Partitioning Problems in Indoor Spaces"],"prefix":"10.3390","volume":"9","author":[{"given":"Sung-Hwan","family":"Kim","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, Pusan National University, Busan 46241, Korea"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9839-7605","authenticated-orcid":false,"given":"Ki-Joune","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Pusan National University, Busan 46241, Korea"}]},{"given":"Hwan-Gue","family":"Cho","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Pusan National University, Busan 46241, Korea"}]}],"member":"1968","published-online":{"date-parts":[[2020,10,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Zhou, R., Lu, S., Chen, J., and Li, Z. (2017, January 5\u20137). An Optimized Space Partitioning Technique to Support Two-Layer WiFi FingerPrinting. Proceedings of the IEEE International Conference on Wireless Communications and Networking, Semarang, Indonesia.","DOI":"10.1109\/WCNC.2017.7925445"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"7619","DOI":"10.1109\/JSEN.2018.2862412","article-title":"An Accurate Geometrical Multi-Target Device-Free Localization Method Using Light Sensors","volume":"18","author":"Zhang","year":"2018","journal-title":"IEEE Sens."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Murata, M., Ahmetovic, D., Sato, D., Takagi, H., Kitani, K.M., and Asakawa, C. (2018, January 19\u201323). Smartphone-based Indoor Localization for Blind Navigation across Building Complexes. Proceedings of the IEEE International Conference on Pervasive Computing and Communications, Athens, Greece.","DOI":"10.1109\/PERCOM.2018.8444593"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Chen, Y., Liu, J., Jaakkola, A., Hyypp\u00e4, J., Chen, L., Hyypp\u00e4, H., Jian, T., and Chen, R. (2014, January 5\u20138). Knowledge-based Indoor Positioning Based on LiDAR aided multile sensors system for UGVs. Proceedings of the IEEE\/ION Position, Location and Navigation Symposium, Monterey, CA, USA.","DOI":"10.1109\/PLANS.2014.6851364"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1080\/19479832.2013.811124","article-title":"3D Building Modeling Using Images and LiDAR: A Review","volume":"4","author":"Wang","year":"2013","journal-title":"Int. J. Image Data Fusion"},{"key":"ref_6","unstructured":"Sun, J., and Li, X. (2015, January 19\u201321). Indoor Evacuation Routes Planning with a Grid Graph-based Model. Proceedings of the 19th Conference on Geoinformatics, Wuhan, China."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.firesaf.2015.08.009","article-title":"Integrating Sensing, Routing and Timing for Indoor Evacuation","volume":"78","author":"Wang","year":"2015","journal-title":"Fire Saf. J."},{"key":"ref_8","unstructured":"Tehrani, M.A., Kleihorst, R., Meijer, P., and Spaanenburg, L. (September, January 30). Abnormal Motion Detection in a Real-time Smart Camera System. Proceedings of the 3rd ACM\/IEEE International Conference on Distributed Smart Cameras (ICDSC), Como, Italy."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Ko, T. (2008, January 15\u201317). A Survey on Behavior Analysis in Video Surveillance for Homeland Security Applications. Proceedings of the 37th IEEE Applied Imagery Pattern Recognition Workshop, Washington, DC, USA.","DOI":"10.1109\/AIPR.2008.4906450"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Jin, P., Du, J., Huang, C., Wan, S., and Yue, L. (2015, January 20\u201323). Detecting Hotspots from Trajactory Data in Indoor Spaces. Proceedings of the International Conference on Database Systems for Advanced Applications, Hanoi, Vietnam.","DOI":"10.1007\/978-3-319-18120-2_13"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Kr\u016bminait\u0117, M., and Zlatanova, S. (2014, January 4). Indoor Space Subdivision for Indoor Navigation. Proceedings of the 6th ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness, Dallas\/Fort Worth, TX, USA.","DOI":"10.1145\/2676528.2676529"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Huh, J.H., and Seo, K. (2017). An Indoor Location-Based Control System Using Bluetooth Beacons for IoT Systems. Sensors, 17.","DOI":"10.3390\/s17122917"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0926-5805(99)00012-6","article-title":"From CAD to Virtual Reality: Modelling Approaches, Data Exchange and Interactive 3D Building Design Tools","volume":"2000","author":"Whyte","year":"2000","journal-title":"Autom. Constr."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1016\/S0010-4485(98)00031-1","article-title":"Generation of 3D Building Models from 2D Architectural Plans","volume":"30","author":"Lewis","year":"1998","journal-title":"Comput. Aided Des."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Ohori, K.A., Diakit\u00e9, A., Krijnen, T., Ledoux, H., and Stoter, J. (2018). Processing BIM and GIS Models in Practice: Experiences and Recommendations from a GeoBIM Project in The Netherlands. Int. J. Geo Inf., 7.","DOI":"10.3390\/ijgi7080311"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.cag.2015.07.008","article-title":"Automatic Reconstruction of Parametric Building Models from Indoor Point Clouds","volume":"54","author":"Ochmann","year":"2016","journal-title":"Comput. Graph."},{"key":"ref_17","unstructured":"Industry Foundation Classes (IFC) for Data Sharing in the Construction and Facility Management Industries (2020, October 22). ISO 16739-1:2018; International Organization for Standardization. Available online: https:\/\/www.iso.org\/standard\/70303.html."},{"key":"ref_18","unstructured":"Gr\u00f6ger, G., Kolbe, T.H., Nagel, C., H\u00e4fele, K.-H., and OGC City Geography Markup Language (CityGML) Encoding Standard (2020, October 22). OGC 12-019; Open Geospatial Consortium. Available online: https:\/\/www.ogc.org\/standards\/citygml."},{"key":"ref_19","unstructured":"Lee, J., Li, K.-J., Zlatanova, S., Kolbe, T.H., Nagel, C., and Becker, T. (2020, October 22). OGC\u00a9 IndoorGML with Corrigendum. OGC 14-005r5; Open Geospatial Consortium. Available online: https:\/\/www.ogc.org\/standards\/indoorgml."},{"key":"ref_20","unstructured":"Konde, A., Tauscher, H., Biljecki, F., and Crawford, J. (2018, January 1\u20132). Floor Plans in CityGML. Proceedings of the 13th 3D GeoInfo Conference, Delft, The Netherlands."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"101453","DOI":"10.1016\/j.compenvurbsys.2019.101453","article-title":"Automatic Geo-referencing of BIM in GIS environments using Building Footprints","volume":"80","author":"Zlatanova","year":"2020","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-004-1092-3","article-title":"Computing Optimal Diameter-Bounded Polygon Partitions","volume":"40","author":"Damian","year":"2004","journal-title":"Algorithmica"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/s002240000101","article-title":"Minimum Convex Partition of Polygon with Holes by Cuts in Given Directions","volume":"31","author":"Lingas","year":"1998","journal-title":"Theory Comput. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1016\/j.dam.2009.12.004","article-title":"Approximation Algorithms for Art Gallery Problems in Polygons","volume":"158","author":"Ghosh","year":"2010","journal-title":"Discret. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2890491","article-title":"Algorithm 966: A Practical Iterative Algorithm for the Art Gallery Problem Using Integer Linear Programming","volume":"43","author":"Tozoni","year":"2016","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/0031-3203(81)90002-9","article-title":"An Efficient Algorithum for Decomposing a Polygon into Star-Shaped Polygons","volume":"13","author":"Avis","year":"1981","journal-title":"Pattern Recognit."},{"key":"ref_27","unstructured":"David, P., Idasiak, V., and Kratz, F. (2007, January 23\u201325). A Sensor Placement Approach for the Mornitoring of Indoor Spaces. Proceedings of the European Conference on Smart Sensing and Context (EUROSSC), Kendal, UK."},{"key":"ref_28","unstructured":"Buchin, M., Mosig, A., and Selbach, L. (2019, January 18\u201320). Skeleton-based Decomposition of Simple Polygons. Proceedings of the 35th European Workshop on Computational Geometry, Utrecht, The Netherlands."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Culberson, J.C., and Reckhow, R.A. (1988, January 24\u201326). Covering Polygon is Hard. Proceedings of the 29th Annual Symposium of Foundations of Computer Science, White Plains, NY, USA.","DOI":"10.1109\/SFCS.1988.21976"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Keil, M. (2000). Polygon decomposition. Handbook of Computational Geometry, North-Holland.","DOI":"10.1016\/B978-044482537-7\/50012-7"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","article-title":"Computational Complexity of Art Gallery Problems","volume":"32","author":"Lee","year":"1986","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1137\/0214056","article-title":"Decomposing a Polygon into Simpler Components","volume":"14","author":"Keil","year":"1985","journal-title":"SIAM J. Comput."},{"key":"ref_33","unstructured":"Huang, H., Ni, C.C., Ban, X., Gao, J., Schneider, A.T., and Lin, S. (May, January 27). Connected Wireless Camera Network Deployment with Visibility Coverage. Proceedings of the IEEE Conference on Computer Communications (INFOCOM), Toronto, ON, Canada."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Rajagopal, N., Chayapathy, S., Sinopoli, B., and Rowe, A. (2016, January 4\u20137). Beacon Placement for Range-Based Indoor Localization. Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), Alcala de Henares, Spain.","DOI":"10.1109\/IPIN.2016.7743626"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Allen, R., MacMillan, N., Marinakis, D., Nishat, R.I., Rahman, R., and Whitesides, S. (2014, January 6\u20139). The Range Beacon Placement Problem for Robot Navigation. Proceedings of the Canadian Conference on Computer and Robot Vision, Montreal, QC, Canada.","DOI":"10.1109\/CRV.2014.28"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1370","DOI":"10.1109\/JIOT.2017.2708719","article-title":"Beacon Deployment for Unambiguous Positioning","volume":"4","author":"He","year":"2017","journal-title":"IEEE Internet Things"},{"key":"ref_37","unstructured":"Yabuta, K., and Kitazawa, H. (2008, January 18\u201321). Optimum Camera Placement Considering Camera Specification for Security Monitoring. Proceedings of the IEEE International Symposium on Circuits and Systems, Seattle, WA, USA."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1109\/TII.2012.2225436","article-title":"Distributed Deployment Strategies for Improved Coverage in a Network of Mobile Sensors With Prioritized Sensing Field","volume":"9","author":"Mahboubi","year":"2013","journal-title":"IEEE Trans. Ind. Inform."},{"key":"ref_39","unstructured":"Zlatanova, S., Liu, L., Sithole, G., Zhao, Z., and Mortari, F. (2014). Space Subdivision for Indoor Applications, Delft University of Technology. Technical Report GISt Report No.66."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"339","DOI":"10.5194\/isprs-archives-XLI-B4-339-2016","article-title":"An Indoor Navigation Approach Considering Obstacles and Space Subdivision of 2D Plan","volume":"41","author":"Xu","year":"2016","journal-title":"Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Habibi, G., Masehain, E., and Beheshti, M.T.H. (2007, January 5\u20138). Binary Integer Programming Model of Point Robot Path Planning. Proceedings of the 33rd Annual Conference of the IEEE Industrial Society (IECON), Taipei, Taiwan.","DOI":"10.1109\/IECON.2007.4460315"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/s12518-019-00273-8","article-title":"An Indoor Navigation Model and Its Network Extraction","volume":"11","author":"Mortari","year":"2019","journal-title":"Appl. Geomat."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1737","DOI":"10.1080\/13658816.2015.1041141","article-title":"Generation of Navigation Graphs for Indoor Space","volume":"29","author":"Yang","year":"2015","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Lin, Z., Xu, Z., Hu, D., Hu, Q., and Li, W. (2017). Hybrid Spatial Data Model for Indoor Space: Combined Topology and Grid. Int. J. Geo Inf., 6.","DOI":"10.3390\/ijgi6110343"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Fr\u00edas, E., D\u00e1z-Vilari\u00f1o, L., Balado, J., and Lorenzo, H. (2019). From BIM to Scan Planning and Optimization for Construction Control. Remote Sens., 11.","DOI":"10.3390\/rs11171963"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Yuan, W., and Schneider, M. (2010, January 23\u201326). Supporting Continuous Range Queries in Indoor Space. Proceedings of the 11th International Conference on Mobile Data Management, Kansas City, MO, USA.","DOI":"10.1109\/MDM.2010.21"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.autcon.2019.03.004","article-title":"An Algorithm to Facet Curved Walls in IFC BIN for Building Energy Analysis","volume":"103","author":"Yin","year":"2019","journal-title":"Autom. Constr."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","article-title":"A Combinatorial Theorem in Plane Geometry","volume":"18","year":"1975","journal-title":"J. Comb. Theory, Ser. B"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Zlatanova, S., Liu, L., and Sithole, G. (2013, January 5). A Conceptual Framework of Space Subdivision for Indoor Navigation. Proceedings of the 5th ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness (ISA), Orlando, FL, USA.","DOI":"10.1145\/2533810.2533819"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/9\/11\/618\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:26:54Z","timestamp":1760178414000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/9\/11\/618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,23]]},"references-count":49,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["ijgi9110618"],"URL":"https:\/\/doi.org\/10.3390\/ijgi9110618","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2020,10,23]]}}}