research-article

Retrieving α-Shapes and Schematic Polygonal Approximations for Sets of Points within Queried Temporal Ranges

Authors:

Annika Bonerath,

Benjamin Niedermann,

Jan-Henrik HaunertAuthors Info & Claims

SIGSPATIAL '19: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Pages 249 - 258

https://doi.org/10.1145/3347146.3359087

Published: 05 November 2019 Publication History

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.

References

[1]

Dominique Attali. 1998. r-regular shape reconstruction from unorganized points. Comput. Geom. 10, 4 (1998), 239--247. https://doi.org/10.1016/S0925-7721(98)00013-3

Digital Library

[2]

Fausto Bernardini and Chandrajit L. Bajaj. 1997. Sampling and reconstructing manifolds using alpha-shapes. In Proc. 9th Canadian Conf. Comput. Geom.

[3]

Kevin Buchin, Wouter Meulemans, André Van Renssen, and Bettina Speckmann. 2016. Area-Preserving Simplification and Schematization of Polygonal Subdivisions. ACM Trans. Spatial Algorithms Syst. 2, 1 (2016), 2:1--2:36. https://doi.org/10.1145/2818373

Digital Library

[4]

Adrish Ray Chaudhuri, Bidyut Baran Chaudhuri, and Swapan K. Parui. 1997. A Novel Approach to Computation of the Shape of a Dot Pattern and Extraction of Its Perceptual Border. Comput. Vis. Image Underst. 68, 3 (1997), 257--275. https://doi.org/10.1006/cviu.1997.0550

Digital Library

[5]

Bernard Chazelle. 1986. Filtering Search: A New Approach to Query-Answering. SIAM J. Comput. 15, 3 (1986), 703--724. https://doi.org/10.1137/0215051

Digital Library

[6]

Serafino Cicerone and Matteo Cermignani. 2012. Fast and Simple Approach for Polygon Schematization. In Computational Science and Its Applications (LNCS), Vol. 7334. Springer, Berlin, Heidelberg, 267--279. https://doi.org/10.1007/978-3-642-31125-3_21

[7]

Mark de Berg, Wouter Meulemans, and Bettina Speckmann. 2011. Delineating Imprecise Regions via Shortest-path Graphs. In Proc. 19th ACM SIGSPATIAL Internat. Conf. Advances in Geographic Information Systems (GLS '11). 271--280. https://doi.org/10.1145/2093973.2094010

Digital Library

[8]

Matt Duckham, Lars Kulik, Michael F. Worboys, and Antony Galton. 2008. Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition 41, 10 (2008), 3224--3236. https://doi.org/10.1016/j.patcog.2008.03.023

Digital Library

[9]

Herbert Edelsbrunner. 1983. A new approach to rectangle intersections part I. Int. J. Comput. Math. 13, 3-4 (1983), 209--219. https://doi.org/10.1080/00207168308803364

[10]

Herbert Edelsbrunner. 1992. Weighted alpha shapes. Technical Report UIUCDCS-R-92-1760. University of Illinois at Urbana-Champaign, Champaign, IL, USA.

Digital Library

[11]

Herbert Edelsbrunner. 2010. Alpha shapes - a survey. Tessellations in the Sciences 27 (2010), 1--25.

[12]

Herbert Edelsbrunner, David G. Kirkpatrick, and Raimund Seidel. 1983. On the shape of a set of points in the plane. IEEE Trans. Information Theory 29, 4 (1983), 551--558. https://doi.org/10.1109/TIT.1983.1056714

Digital Library

[13]

Eugene Fink and Derick Wood. 2004. Restricted-Orientation Convexity. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18849-7

[14]

Christopher B. Jones, Ross S. Purves, Paul D. Clough, and Hideo Joho. 2008. Modelling vague places with knowledge from the Web. Int. J. Geogr. Inf. Sci. 22, 10 (2008), 1045--1065. https://doi.org/10.1080/13658810701850547

Digital Library

[15]

D. Krasnoshchekov and V. Polishchuk. 2008. Robust curve reconstruction with k-order alpha-shapes. In IEEE Internat. Conf. Shape Modeling and Applications. 279--280. https://doi.org/10.1109/SMI.2008.4548006

[16]

Dmitry N. Krasnoshchekov and Valentin Polishchuk. 2014. Order-k alpha-hulls and alpha-shapes. Inf. Process. Lett. 114, 1-2 (2014), 76--83. https://doi.org/10.1016/j.ipl.2013.07.023

[17]

Jie Liang, Herbert Edelsbrunner, Ping Fu, Pamidighantam V. Sudhakar, and Shankar Subramaniam. 1998. Analytical shape computation of macromolecules: I. Molecular area and volume through alpha shape. Proteins: Structure, Function, and Bioinformatics 33, 1 (1998), 1--17. https://doi.org/10.1002/(SICI)1097-0134(19981001)33:13.3.CO;2-9

[18]

Wouter Meulemans, André van Renssen, and Bettina Speckmann. 2010. Area-Preserving Subdivision Schematization. In Geographic Information Science, GL-Science 2010 (LNCS), Vol. 6292. Springer, Berlin, Heidelberg, 160--174. https://doi.org/10.1007/978-3-642-15300-6_12

[19]

Dongliang Peng and Alexander Wolff. 2014. Watch Your Data Structures!. In Proc. 22nd Annual GIS Research UK Conf. (GISRUK).

[20]

PostgreSQL Global Development Group. 2018. PostgreSQL 11.0 Documentation.

[21]

Ross Purves, Paul Clough, and Hideo Joho. 2005. Identifying imprecise regions for geographic information retrieval using the web. In Proc. 13th Annual GIS Research UK Conf. (GISRUK). 313--18.

[22]

Arthur van Goethem, Wouter Meulemans, Bettina Speckmann, and Jo Wood. 2015. Exploring Curved Schematization of Territorial Outlines. IEEE Trans. Vis. Comput. Graph. 21, 8 (2015), 889--902. https://doi.org/10.1109/TVCG.2015.2401025

[23]

Jari Vauhkonen, Ilkka Korpela, Matti Maltamo, and Timo Tokola. 2010. Imputation of single-tree attributes using airborne laser scanning-based height, intensity, and alpha shape metrics. Remote Sensing of Environment 114, 6 (2010), 1263--1276.

Cited By

Forsch AHaunert J(2024)Metrochrones: Schematic Isochrones for Schematic Metro MapsThe Cartographic Journal10.1080/00087041.2023.228443660:4(383-401)Online publication date: 23-Jul-2024
https://doi.org/10.1080/00087041.2023.2284436
Forsch AKemna RLangetepe EHaunert J(2024)Polyline Morphing for Animated Schematic MapsJournal of Geovisualization and Spatial Analysis10.1007/s41651-024-00198-w8:2Online publication date: 8-Oct-2024
https://doi.org/10.1007/s41651-024-00198-w
Bonerath AHaunert JMitchell JNiedermann B(2023)Shortcut Hulls: Vertex-restricted Outer Simplifications of PolygonsComputational Geometry10.1016/j.comgeo.2023.101983(101983)Online publication date: Jan-2023
https://doi.org/10.1016/j.comgeo.2023.101983
Show More Cited By

Index Terms

Retrieving α-Shapes and Schematic Polygonal Approximations for Sets of Points within Queried Temporal Ranges

Recommendations

A Time-Windowed Data Structure for Spatial Density Maps
SIGSPATIAL '20: Proceedings of the 28th International Conference on Advances in Geographic Information Systems

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 ...
Exploiting Embedded Synopsis for Exact and Approximate Query Processing
Database and Expert Systems Applications
Abstract
Organizing data in structured forms is a mainstream approach to improve the efficiency of query processing on database. For example, a B+Tree index is widely employed to limit the search space for selective queries, speeding up the query ...
Compact representation for answer sets of n-ary regular queries

An n-ary query over trees takes an input tree t and returns a set of n-tuples of the nodes of t. In this paper, a compact data structure is introduced for representing the answer sets of n-ary queries defined by tree automata. Despite that the number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '19: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2019

648 pages

ISBN:9781450369091

DOI:10.1145/3347146

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Deutsche Forschungsgemeinschaft

Conference

SIGSPATIAL '19

Sponsor:

SIGSPATIAL

SIGSPATIAL '19: 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 5 - 8, 2019

IL, Chicago, USA

Acceptance Rates

SIGSPATIAL '19 Paper Acceptance Rate 34 of 161 submissions, 21%;

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
223
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)4

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Forsch AHaunert J(2024)Metrochrones: Schematic Isochrones for Schematic Metro MapsThe Cartographic Journal10.1080/00087041.2023.228443660:4(383-401)Online publication date: 23-Jul-2024
https://doi.org/10.1080/00087041.2023.2284436
Forsch AKemna RLangetepe EHaunert J(2024)Polyline Morphing for Animated Schematic MapsJournal of Geovisualization and Spatial Analysis10.1007/s41651-024-00198-w8:2Online publication date: 8-Oct-2024
https://doi.org/10.1007/s41651-024-00198-w
Bonerath AHaunert JMitchell JNiedermann B(2023)Shortcut Hulls: Vertex-restricted Outer Simplifications of PolygonsComputational Geometry10.1016/j.comgeo.2023.101983(101983)Online publication date: Jan-2023
https://doi.org/10.1016/j.comgeo.2023.101983
Bill RBlankenbach JBreunig MHaunert JHeipke CHerle SMaas HMayer HMeng LRottensteiner FSchiewe JSester MSörgel UWerner M(2022)Geospatial Information Research: State of the Art, Case Studies and Future PerspectivesPFG – Journal of Photogrammetry, Remote Sensing and Geoinformation Science10.1007/s41064-022-00217-990:4(349-389)Online publication date: 19-Sep-2022
https://doi.org/10.1007/s41064-022-00217-9
Forsch ADehbi YNiedermann BOehrlein JRottmann PHaunert J(2021)Multimodal travel‐time maps with formally correct and schematic isochronesTransactions in GIS10.1111/tgis.1282125:6(3233-3256)Online publication date: 31-Aug-2021
https://doi.org/10.1111/tgis.12821
Bonerath ANiedermann BDiederich JOrgeig YOehrlein JHaunert J(2020)A Time-Windowed Data Structure for Spatial Density MapsProceedings of the 28th International Conference on Advances in Geographic Information Systems10.1145/3397536.3422242(15-24)Online publication date: 3-Nov-2020
https://dl.acm.org/doi/10.1145/3397536.3422242
Alegría COrden DSeara CUrrutia J(2020)Efficient computation of minimum-area rectilinear convex hull under rotation and generalizationsJournal of Global Optimization10.1007/s10898-020-00953-5Online publication date: 7-Oct-2020
https://doi.org/10.1007/s10898-020-00953-5

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents