doi:10.4230/LIPIcs.GD.2024.22

@inproceedings{Bonerath_GD_2024,
    address = {Dagstuhl, Germany},
    annote = {Keywords: External labeling, Orthoradial drawing, NP-hardness, Polynomial algorithms},
    author = {Bonerath, Annika and N\"{o}llenburg, Martin and Terziadis, Soeren and Wallinger, Markus and Wulms, Jules},
    booktitle = {32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
    doi = {10.4230/LIPIcs.GD.2024.22},
    editor = {Felsner, Stefan and Klein, Karsten},
    isbn = {978-3-95977-343-0},
    issn = {1868-8969},
    pages = {22:1--22:17},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    title = {{Boundary Labeling in a Circular Orbit}},
    url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.22},
    urn = {urn:nbn:de:0030-drops-213060},
    volume = {320},
    year = {2024}
}

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.

doi:10.4230/LIPIcs.ESA.2024.90

@inproceedings{NaumannEtAl2024,
    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.},
    author = {Naumann, Alexander and Bonerath, Annika and Haunert, Jan-Henrik},
    booktitle = {Proc. European Symposium on Algorithms (ESA'24)},
    doi = {10.4230/LIPIcs.ESA.2024.90},
    pages = {90:1--90:15},
    title = {Many-to-many polygon matching \`{a} la {Jaccard}},
    year = {2024}
}

@inproceedings{b-oolcc-preprint-24,
    author = {Bonerath, Annika and N{\"o}llenburg, Martin and Terziadis, Soeren and Wallinger, Markus and Wulms, Jules},
    booktitle = {Proceedings of the 40th European Workshop on Computational Geometry (EuroCG'24)},
    note = {Preprint.},
    title = {{On Orbital Labeling with Circular Contours}},
    url = {https://eurocg2024.math.uoi.gr/data/uploads/paper_67.pdf},
    year = {2024}
}

doi:10.1145/3615891.3628012

@inproceedings{inproceedings,
    address = {Hamburg, Germany},
    author = {Bonerath, Annika and Orgeig, Yannick and Haunert, Jan-Henrik and Dehbi, Youness},
    booktitle = {Proceedings of the 6th ACM SIGSPATIAL International Workshop on GeoSpatial Simulation},
    doi = {10.1145/3615891.3628012},
    month = {11},
    pages = {19-22},
    title = {Integrating Optimization-Based Spatial Unit Allocation into a Multi-Agent Model for the Simulation of Urban Growth},
    year = {2023}
}

doi:10.5194/ica-adv-4-1-2023

@article{bonerath2023thetastarstructure,
    author = {Bonerath, A. and Dong, Y. and Haunert, J.-H.},
    doi = {10.5194/ica-adv-4-1-2023},
    journal = {Advances in Cartography and GIScience of the ICA},
    note = {Special issue of 31st International Cartographic Conference (ICC'23)},
    pages = {1},
    title = {An Efficient Data Structure Providing Maps of the Frequency of Public Transit Service Within User-Specified Time Windows},
    url = {https://ica-adv.copernicus.org/articles/4/1/2023/},
    volume = {4},
    year = {2023}
}

Let P be a polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another polygon that encloses P and whose oriented boundary is composed of elements from C. We require P and the output shortcut hull to be weakly simple polygons, which we define as a generalization of simple polygons. Shortcut hulls find their application in cartography, where a common task is to compute simplified representations of area features. We aim at a shortcut hull that has a small area and a small perimeter. Our optimization objective is to minimize a convex combination of these two criteria. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via computation of shortest paths. For the more challenging case in which the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon's exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for the schematization of polygons.

doi:https://doi.org/10.1016/j.comgeo.2023.101983

@article{BONERATH2023101983,
    abstract = {Let P be a polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another polygon that encloses P and whose oriented boundary is composed of elements from C. We require P and the output shortcut hull to be weakly simple polygons, which we define as a generalization of simple polygons. Shortcut hulls find their application in cartography, where a common task is to compute simplified representations of area features. We aim at a shortcut hull that has a small area and a small perimeter. Our optimization objective is to minimize a convex combination of these two criteria. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via computation of shortest paths. For the more challenging case in which the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon's exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for the schematization of polygons.},
    author = {Annika Bonerath and Jan-Henrik Haunert and Joseph S.B. Mitchell and Benjamin Niedermann},
    doi = {https://doi.org/10.1016/j.comgeo.2023.101983},
    issn = {0925-7721},
    journal = {Computational Geometry Theory and Applications},
    pages = {101983},
    title = {Shortcut Hulls: Vertex-restricted Outer Simplifications of Polygons},
    url = {https://www.sciencedirect.com/science/article/pii/S0925772123000032},
    year = {2023}
}

@inproceedings{rottmann2022mosaicsets_compcart,
    address = {Bonn},
    author = {Peter Rottmann and Makus Wallinger and Annika Bonerath and Sven Gedicke and Martin Nöllenburg and Jan-Henrik Haunert},
    booktitle = {Abstracts of 1st Workshop on Computational Cartography 2022},
    month = {may},
    title = {{M}osaic{S}ets: {E}mbedding {S}et {S}ystems into {G}rid {G}raphs},
    year = {2022}
}

Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets : a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews.

doi:10.1109/TVCG.2022.3209485

@article{rottmann2022mosaicsets,
    abstract = {Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets : a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews.},
    author = {Peter Rottmann and Makus Wallinger and Annika Bonerath and Sven Gedicke and Martin Nöllenburg and Jan-Henrik Haunert},
    doi = {10.1109/TVCG.2022.3209485},
    journal = {IEEE Transactions on Visualization and Computer Graphics},
    number = {1},
    pages = {875-885},
    publisher = {IEEE},
    title = {MosaicSets: Embedding set systems into grid graphs},
    volume = {29},
    year = {2022}
}

@inproceedings{bonerath2022thetastructure,
    address = {Bonn},
    author = {Annika Bonerath and Benjamin Niedermann and Jim Diederich and Yu Dong and Yannick Orgeig and Johannes Oehrlein and Jan-Henrik Haunert},
    booktitle = {Abstracts of 1st Workshop on Computational Cartography 2022},
    month = {may},
    title = {Theta Structure: A Time-Windowed Data Structure for the Spatial Visualization of Event Densities},
    year = {2022}
}

doi:10.5194/ica-abs-5-96-2022

@article{bonerath2022spatiotemporal,
    address = {Vienna},
    author = {Bonerath, Annika and Temerowski, Lukas and Gedicke, Sven and Haunert, Jan-Henrik},
    doi = {10.5194/ica-abs-5-96-2022},
    journal = {Abstracts of the ICA},
    month = {sep},
    pages = {96},
    title = {{E}xploring {S}patio-{T}emporal {E}vent {D}ata on a {S}mart {W}atch},
    volume = {5},
    year = {2022}
}

Let P be a crossing-free polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another crossing-free polygon that encloses P and whose oriented boundary is composed of elements from C. Shortcut hulls find their application in geo-related problems such as the simplification of contour lines. We aim at a shortcut hull that linearly balances the enclosed area and perimeter. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via shortest paths. For the more challenging case that the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon’s exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for drawing the rough extent of point sets as well as for the schematization of polygons.

@inproceedings{Haunert2021,
    abstract = {Let P be a crossing-free polygon and C a set of shortcuts,
where each shortcut is a directed straight-line segment
connecting two vertices of P. A shortcut hull of
P is another crossing-free polygon that encloses P and
whose oriented boundary is composed of elements from
C. Shortcut hulls find their application in geo-related
problems such as the simplification of contour lines. We
aim at a shortcut hull that linearly balances the enclosed
area and perimeter. If no holes in the shortcut hull
are allowed, the problem admits a straight-forward solution
via shortest paths. For the more challenging case
that the shortcut hull may contain holes, we present a
polynomial-time algorithm that is based on computing
a constrained, weighted triangulation of the input polygon’s
exterior. We use this problem as a starting point
for investigating further variants, e.g., restricting the
number of edges or bends. We demonstrate that shortcut
hulls can be used for drawing the rough extent of
point sets as well as for the schematization of polygons.},
    author = {Annika Bonerath and Jan-Henrik Haunert and Joseph S. B. Mitchell and Benjamin Niedermann},
    booktitle = {Proceedings of the 33rd Canadian Conference on Computational Geometry},
    editor = {Meng He and Don Sheehy},
    pages = {12-23},
    title = {Shortcut Hulls: Vertex-restricted Outer Simplifications of Polygons},
    url = {https://projects.cs.dal.ca/cccg2021/wordpress/wp-content/uploads/2021/08/CCCG2021.pdf},
    year = {2021}
}

Visualizing spatial data on small-screen devices such as smartphones and smartwatches poses new challenges in computational cartography. The current interfaces for map exploration require their users to zoom in and out frequently. Indeed, zooming and panning are tools suitable for choosing the map extent corresponding to an area of interest. They are not as suitable, however, for resolving the graphical clutter caused by a high feature density since zooming in to a large map scale leads to a loss of context. Therefore, in this paper, we present new external labeling methods that allow a user to navigate through dense sets of points of interest while keeping the current map extent fixed. We provide a unified model, in which labels are placed at the boundary of the map and visually associated with the corresponding features via connecting lines, which are called leaders. Since the screen space is limited, labeling all features at the same time is impractical. Therefore, at any time, we label a subset of the features. We offer interaction techniques to change the current selection of features systematically and, thus, give the user access to all features. We distinguish three methods, which allow the user either to slide the labels along the bottom side of the map or to browse the labels based on pages or stacks. We present a generic algorithmic framework that provides us with the possibility of expressing the different variants of interaction techniques as optimization problems in a unified way. We propose both exact algorithms and fast and simple heuristics that solve the optimization problems taking into account different criteria such as the ranking of the labels, the total leader length as well as the distance between leaders. In experiments on real-world data we evaluate these algorithms and discuss the three variants with respect to their strengths and weaknesses proving the flexibility of the presented algorithmic framework.

doi:10.1109/TVCG.2020.3030399

@article{gbnh-zm-21,
    abstract = {Visualizing spatial data on small-screen devices such as
smartphones and smartwatches poses new challenges in computational
cartography. The current interfaces for map exploration require
their users to zoom in and out frequently. Indeed, zooming and
panning are tools suitable for choosing the map extent corresponding
to an area of interest. They are not as suitable, however, for
resolving the graphical clutter caused by a high feature
density since zooming in to a large map scale leads to a loss of
context. Therefore, in this paper, we present new external labeling methods that allow a user to navigate through dense sets of
points of interest while keeping the current map extent fixed. We provide a unified model, in which labels are
placed at the boundary of the map and visually associated with the
corresponding features via connecting lines, which are called
leaders. Since the screen space is limited, labeling all features
at the same time is impractical. Therefore, at any time, we label a
subset of the features. We offer interaction techniques to change
the current selection of features systematically and, thus, give the
user access to all features. We distinguish three methods, which
allow the user either to slide the labels along the bottom side of the map or
to browse the labels based on pages or stacks. We present a generic
algorithmic framework that provides us with the possibility of
expressing the different variants of interaction techniques as
optimization problems in a unified way. We propose both exact
algorithms and fast and simple heuristics that solve the
optimization problems taking into account different criteria such as
the ranking of the labels, the total leader length as well as the
distance between leaders. In experiments on real-world data we
evaluate these algorithms and discuss the three variants with
respect to their strengths and weaknesses proving the flexibility of
the presented algorithmic framework.},
    author = {Gedicke, Sven and Bonerath, Annika and Niedermann, Benjamin and Haunert, Jan-Henrik},
    doi = {10.1109/TVCG.2020.3030399},
    journal = {IEEE Transactions on Visualization and Computer Graphics},
    note = {https://youtu.be/IuMhk8jp54c},
    number = {2},
    pages = {1247--1256},
    title = {{Z}oomless {M}aps: {E}xternal {L}abeling {M}ethods for the {I}nteractive {E}xploration of {D}ense {P}oint {S}ets at a {F}ixed {M}ap {S}cale},
    volume = {27},
    year = {2021}
}

The visualization of spatio-temporal data helps researchers understand global processes such as animal migration. In particular, interactively restricting the data to different time windows reveals new insights into the short-term and long-term changes of the research data. Inspired by this use case, we consider the visualization of point data annotated with time stamps. We pick up classical, grid-based density maps as the underlying visualization technique and enhance them with an efficient data structure for arbitrarily specified time-window queries. The running time of the queries is logarithmic in the total number of points and linear in the number of actually colored cells. In experiments on real-world data we show that the data structure answers time-window queries within milliseconds, which supports the interactive exploration of large point sets. Further, the data structure can be used to visualize additional decision problems, e.g., it can answer whether the sum or maximum of additional weights given with the points exceed a certain threshold. We have defined the data structure general enough to also support multiple thresholds expressed by different colors.

doi:10.1145/3397536.3422242

@inproceedings{bhn-twdssdm-20,
    abstract = {The visualization of spatio-temporal data helps researchers
understand global processes such as animal migration. In particular,
interactively restricting the data to different time windows reveals
new insights into the short-term and long-term changes of the
research data. Inspired by this use case, we consider the
visualization of point data annotated with time stamps. We pick up
classical, grid-based density maps as the underlying visualization
technique and enhance them with an efficient data structure for
arbitrarily specified time-window queries. The running time of the
queries is logarithmic in the total number of points and linear in
the number of actually colored cells. In experiments on real-world
data we show that the data structure answers time-window queries
within milliseconds, which supports the interactive exploration of large
point sets. Further, the data structure can be used to visualize
additional decision problems, e.g., it can answer whether
the sum or maximum of additional weights given with the points
exceed a certain threshold. We have defined the data structure
general enough to also support multiple thresholds expressed by
different colors.},
    author = {Bonerath, A. and Niedermann, B. and Diederich, J. and Orgeig, Y. and Oehrlein, J. and Haunert, J.-H.},
    booktitle = {Proc. 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '20)},
    doi = {10.1145/3397536.3422242},
    pages = {15--24},
    title = {{A Time-Windowed Data Structure for Spatial Density Maps}},
    year = {2020}
}

A polygon is called C-oriented if the orientations of all its edges stem from a pre-defined set C. The schematization of a polygon is then a C-oriented polygon that describes and simplifies the shape of the input polygon with respect to given hard and soft constraints. We study the case that the C-oriented polygon needs to contain the input polygon such that it is tight in the sense that it cannot be shrunk without starting to overlap with the input polygon; we call this a tight C-hull of the polygon. We restrict the tight C-hull to be a simple polygon. We aim at a tight C-hull that optimally balances the number of bends, the total edge length and the enclosed area. For the case that both polygons are rectilinear, we present a dynamic-programming approach that yields such a tight hull in polynomial time. For arbitrary simple polygons we can use the same approach to obtain approximate tight rectilinear hulls.

@inproceedings{bhn-trhsp-20,
    abstract = {A polygon is called C-oriented if the orientations of all its edges stem from a pre-defined set C.
The schematization of a polygon is then a C-oriented polygon that describes and simplifies the shape of the input polygon with respect to given hard and soft constraints.
We study the case that the C-oriented polygon needs to contain the input polygon such that it is tight in the sense that it cannot be shrunk without starting to overlap
with the input polygon; we call this a tight C-hull of the polygon. We restrict the tight C-hull to be a simple polygon. We aim at a tight C-hull that optimally balances
the number of bends, the total edge length and the enclosed area. For the case that both polygons are rectilinear, we present a dynamic-programming approach that yields
such a tight hull in polynomial time. For arbitrary simple polygons we can use the same approach to obtain approximate tight rectilinear hulls.},
    author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.},
    booktitle = {Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)},
    note = {trailer: https://youtu.be/GZTS5fs0FG4, presentation: https://youtu.be/B392e75WK2U},
    title = {{Tight Rectilinear Hulls of Simple Polygons}},
    url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/eurocg20_proceedings.pdf},
    year = {2020}
}

In the context of research data management, the interactive exploration of data is a useful tool to make data findable and reusable. For exploring spatio- and temporal data we developed in a previously published work a data structure that provides the user with simple visualizations of the data for time window queries. We considered the data to be points in space each associated with a time stamp and we visualized it using \alpha-shapes, which generalize convex hulls. In general, time windowed data structures support time window queries for geometric shapes or more general problems from computational geometry such as counting and intersection problems. With this paper, we contribute a review of our previously published method in the context of time windowed data structures, which is a relatively new concept of computational geometry. In particular, we highlight the relevance of our work for a growing domain of research.

@inproceedings{bhn-dagoierd20,
    abstract = {In the context of research data management, the interactive exploration of data is a useful tool to make data findable and reusable. For exploring spatio- and temporal data we developed in a previously published work a data structure that provides the user with simple visualizations of the data for time window queries. We considered the data to be points in space each associated with a time stamp and we visualized it using \alpha-shapes, which generalize convex hulls. In general, time windowed data structures support time window queries for geometric shapes or more general problems from computational geometry such as counting and intersection problems. With this paper, we contribute a review of our previously published method in the context of time windowed data structures, which is a relatively new concept of computational geometry. In particular, we highlight the relevance of our work for a growing domain of research.},
    author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.},
    booktitle = {Publikationen der Deutschen Gesellschaft f\"ur Photogrammetrie, Fernerkundung und Geoinformation e.V., DGPF Jahrestagung 2020, Stuttgart, Germany},
    number = {0},
    pages = {488--496},
    title = {Dynamic Aggregation of Geo-Objects for the Interactive Exploration of Research Data},
    volume = {29},
    year = {2020}
}

The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. In this paper we consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data.

@inproceedings{bhn-castrqps-19,
    abstract = {The interactive exploration of data requires data structures that can be repeatedly queried to
obtain simple visualizations of parts of the data. In this paper we consider the scenario that the
data is a set of points each associated with a time stamp and that the result of each query is
visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing
each shape independently, we suggest and analyze a simple data structure that aggregates the
α-shapes of all possible queries. Once the data structure is built, it particularly allows us to
query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly
produce small previews of the queried data.},
    author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.},
    booktitle = {Proceedings of the 35rd European Workshop on Computational Geometry (EuroCG'19)},
    note = {Preprint.},
    title = {{Computing alpha-Shapes for Temporal Range Queries on Point Sets}},
    year = {2019}
}

The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. We consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data. We discuss the data structure for the original α-shapes as well as for a schematized version of α-shapes, which further simplifies the visualization. We evaluate the data structure on real-world data. The experiments indicate linear memory consumption with respect to the number of points, which makes the data structure applicable in practice, although the size is quadratic for a theoretic worst case example.

doi:10.1145/3347146.3359087

@inproceedings{bhn-rasspa-19,
    abstract = {The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. We consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data. We discuss the data structure for the original α-shapes as well as for a schematized version of α-shapes, which further simplifies the visualization. We evaluate the data structure on real-world data. The experiments indicate linear memory consumption with respect to the number of points, which makes the data structure applicable in practice, although the size is quadratic for a theoretic worst case example.},
    author = {Bonerath, A. and Niedermann, B. and Haunert, J.-H.},
    booktitle = {Proc. 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '19)},
    doi = {10.1145/3347146.3359087},
    note = {trailer: https://youtu.be/mlnUDhbMSfQ},
    pages = {249--258},
    title = {{Retrieving alpha-Shapes and Schematic Polygonal Approximations for Sets of Points within Queried Temporal Ranges}},
    year = {2019}
}