Optimal simplification of building ground plans

J.H. Haunert, A. Wolff

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


This paper presents an optimization approach to simplify building ground plans given by two-dimensional polygons. We define a simplified building as a subsequence of the original building edges; its vertices are defined by intersections of consecutive (and possibly extended) edges in the selected sequence. Our aim is to minimize the number of edges subject to a user-defined error tolerance. We prove that this problem is NP-hard when requiring that the output consists of non-intersecting simple polygons. Thus we cannot hope for an efficient, exact algorithm. Instead, we propose a heuristic and an integer programming formulation that can be used to solve the problem with existing optimization software. We discuss results of our algorithms and how to incorporate more sophisticated objective functions into our model.
Original languageEnglish
Title of host publicationProceedings 21st Congress of the International Society for Photogrammetry and Remote Sensing (ISPRS'08, Beijing, China, July 3-11, 2008)
PublisherInternational Society of Photogrammetry and Remote Sensing (ISPRS)
Publication statusPublished - 2008

Publication series

NameThe International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences
ISSN (Print)1682-1750


Dive into the research topics of 'Optimal simplification of building ground plans'. Together they form a unique fingerprint.

Cite this