DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.90

Many-To-Many Polygon Matching à La Jaccard

Authors: Alexander Naumann, Annika Bonerath, and Jan-Henrik Haunert

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

Integration of spatial data is a major field of research. An important task of data integration is finding correspondences between entities. Here, we focus on combining building footprint data from cadastre and from volunteered geographic information, in particular OpenStreetMap. Previous research on this topic has led to exact 1:1 matching approaches and heuristic m:n matching approaches, most of which are lacking a mathematical problem definition. We introduce a model for many-to-many polygon matching based on the well-established Jaccard index. This is a natural extension to the existing 1:1 matching approaches. We show that the problem is NP-complete and a naive approach via integer programming fails easily. By analyzing the structure of the problem in detail, we can reduce the number of variables significantly. This approach yields an optimal m:n matching even for large real-world instances with appropriate running time. In particular, for the set of all building footprints of the city of Bonn (119,300 / 97,284 polygons) it yielded an optimal solution in approximately 1 hour.

Cite as

Alexander Naumann, Annika Bonerath, and Jan-Henrik Haunert. Many-To-Many Polygon Matching à La Jaccard. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 90:1-90:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{naumann_et_al:LIPIcs.ESA.2024.90,
  author =	{Naumann, Alexander and Bonerath, Annika and Haunert, Jan-Henrik},
  title =	{{Many-To-Many Polygon Matching \`{a} La Jaccard}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{90:1--90:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.90},
  URN =		{urn:nbn:de:0030-drops-211614},
  doi =		{10.4230/LIPIcs.ESA.2024.90},
  annote =	{Keywords: polygon matching, exact algorithm, Jaccard index}
}

Document

DOI: 10.4230/DagRep.12.11.66

Set Visualization and Uncertainty (Dagstuhl Seminar 22462)

Authors: Susanne Bleisch, Steven Chaplick, Jan-Henrik Haunert, Eva Mayr, Marc van Kreveld, and Annika Bonerath

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)

Abstract

The Dagstuhl Seminar on Set Visualization and Uncertainty brought together a group of researchers from diverse disciplines, all of which are interested in various aspects of this type of visualization: the cognitive aspects, the modelling aspects, the algorithmic aspects, and the information visualization aspects. An important but difficult to handle problem is how one should visualize information with underlying uncertainty. The seminar focused on uncertainty in set systems. This report includes short abstracts of the talks given during the seminar as well as more extensive working group reports on the research done during the seminar.

Cite as

Susanne Bleisch, Steven Chaplick, Jan-Henrik Haunert, Eva Mayr, Marc van Kreveld, and Annika Bonerath. Set Visualization and Uncertainty (Dagstuhl Seminar 22462). In Dagstuhl Reports, Volume 12, Issue 11, pp. 66-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{bleisch_et_al:DagRep.12.11.66,
  author =	{Bleisch, Susanne and Chaplick, Steven and Haunert, Jan-Henrik and Mayr, Eva and van Kreveld, Marc and Bonerath, Annika},
  title =	{{Set Visualization and Uncertainty (Dagstuhl Seminar 22462)}},
  pages =	{66--95},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Bleisch, Susanne and Chaplick, Steven and Haunert, Jan-Henrik and Mayr, Eva and van Kreveld, Marc and Bonerath, Annika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.66},
  URN =		{urn:nbn:de:0030-drops-178360},
  doi =		{10.4230/DagRep.12.11.66},
  annote =	{Keywords: cartography, graph drawing, information visualization, set visualization, uncertainty}
}

Search Results

Documents authored by Bonerath, Annika

Many-To-Many Polygon Matching à La Jaccard

Abstract

Cite as

Set Visualization and Uncertainty (Dagstuhl Seminar 22462)

Abstract

Cite as

Thanks for your feedback!

Could not send message