Search Results

Documents authored by Meulemans, Wouter

Document
DOI: 10.4230/LIPIcs.COSIT.2024.8
Scalable Harmonious Simplification of Isolines

Authors: Steven van den Broek, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
Isolines visually characterize scalar fields by connecting all points of the same value by a closed curve at repeated intervals. They work only as a set which gives the viewer an indication of the shape of the underlying field. Hence, when simplifying isolines it is important that the correspondence - the harmony - between adjacent isolines is preserved whenever it is present. The majority of state-of-the-art simplification methods treat isolines independently; at best they avoid collisions between adjacent simplified isolines. A notable exception is the work by Van Goethem et al. (2021) who were the first to introduce the concept of harmony between adjacent isolines explicitly as an algorithmic design principle. They presented a proof-of-concept algorithm that harmoniously simplifies a sequence of polylines. However, the sets of isolines of scalar fields, most notably terrain, consist of closed curves which are nested in arbitrarily complex ways and not of an ordered sequence of polylines. In this paper we significantly extend the work by Van Goethem et al. (2021) to capture harmony in general sets of isolines. Our new simplification algorithm can handle sets of isolines describing arbitrary scalar fields and is more efficient, allowing us to harmoniously simplify terrain with hundreds of thousands of vertices. We experimentally compare our method to the results of Van Goethem et al. (2021) on bundles of isolines and to general simplification methods on isolines extracted from DEMs of Antartica. Our results indicate that our method efficiently preserves the harmony in the simplified maps, which are thereby less noisy, cartographically more meaningful, and easier to read.
Cite as

Steven van den Broek, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann. Scalable Harmonious Simplification of Isolines. In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vandenbroek_et_al:LIPIcs.COSIT.2024.8,
  author =	{van den Broek, Steven and Meulemans, Wouter and Reimer, Andreas and Speckmann, Bettina},
  title =	{{Scalable Harmonious Simplification of Isolines}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.8},
  URN =		{urn:nbn:de:0030-drops-208230},
  doi =		{10.4230/LIPIcs.COSIT.2024.8},
  annote =	{Keywords: Simplification, isolines, harmony}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.24
Optimizing Symbol Visibility Through Displacement

Authors: Bernd Gärtner, Vishwas Kalani, Meghana M. Reddy, Wouter Meulemans, Bettina Speckmann, and Miloš Stojaković

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
In information visualization, the position of symbols often encodes associated data values. When visualizing data elements with both a numerical and a categorical dimension, positioning in the categorical axis admits some flexibility. This flexibility can be exploited to reduce symbol overlap, and thereby increase legibility. In this paper we initialize the algorithmic study of optimizing symbol legibility via a limited displacement of the symbols. Specifically, we consider unit square symbols that need to be placed at specified y-coordinates. We optimize the drawing order of the symbols as well as their x-displacement, constrained within a rectangular container, to maximize the minimum visible perimeter over all squares. If the container has width and height at most 2, there is a point that stabs all squares. In this case, we prove that a staircase layout is arbitrarily close to optimality and can be computed in O(nlog n) time. If the width is at most 2, there is a vertical line that stabs all squares, and in this case, we give a 2-approximation algorithm (assuming fixed container height) that runs in O(nlog n) time. As a minimum visible perimeter of 2 is always trivially achievable, we measure this approximation with respect to the visible perimeter exceeding 2. We show that, despite its simplicity, the algorithm gives asymptotically optimal results for certain instances.
Cite as

Bernd Gärtner, Vishwas Kalani, Meghana M. Reddy, Wouter Meulemans, Bettina Speckmann, and Miloš Stojaković. Optimizing Symbol Visibility Through Displacement. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.SWAT.2024.24,
  author =	{G\"{a}rtner, Bernd and Kalani, Vishwas and M. Reddy, Meghana and Meulemans, Wouter and Speckmann, Bettina and Stojakovi\'{c}, Milo\v{s}},
  title =	{{Optimizing Symbol Visibility Through Displacement}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.24},
  URN =		{urn:nbn:de:0030-drops-200643},
  doi =		{10.4230/LIPIcs.SWAT.2024.24},
  annote =	{Keywords: symbol placement, visibility, jittering, stacking order}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2023.10
Data-Spatial Layouts for Grid Maps

Authors: Nathan van Beusekom, Wouter Meulemans, Bettina Speckmann, and Jo Wood

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Grid maps are a well-known technique to visualize data associated with spatial regions. A grid map assigns each region to a tile in a grid (often orthogonal or hexagonal) and then represents the associated data values within this tile. Good grid maps represent the underlying geographic space well: regions that are geographically close are close in the grid map and vice versa. Though Tobler’s law suggests that spatial proximity relates to data similarity, local variations may obscure clusters and patterns in the data. For example, there are often clear differences between urban centers and adjacent rural areas with respect to socio-economic indicators. To get a better view of the data distribution, we propose grid-map layouts that take data values into account and place regions with similar data into close proximity. In the limit, such a data layout is essentially a chart and loses all spatial meaning. We present an algorithm to create hybrid layouts, allowing for trade-offs between data values and geographic space when assigning regions to tiles. Our algorithm also handles hierarchical grid maps and allows us to focus either on data or on geographic space on different levels of the hierarchy. Leveraging our algorithm we explore the design space of (hierarchical) grid maps with a hybrid layout and their semantics.
Cite as

Nathan van Beusekom, Wouter Meulemans, Bettina Speckmann, and Jo Wood. Data-Spatial Layouts for Grid Maps. In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanbeusekom_et_al:LIPIcs.GIScience.2023.10,
  author =	{van Beusekom, Nathan and Meulemans, Wouter and Speckmann, Bettina and Wood, Jo},
  title =	{{Data-Spatial Layouts for Grid Maps}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.10},
  URN =		{urn:nbn:de:0030-drops-189052},
  doi =		{10.4230/LIPIcs.GIScience.2023.10},
  annote =	{Keywords: Grid map, algorithms, trade-offs}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.7
Coordinated Schematization for Visualizing Mobility Patterns on Networks

Authors: Bram Custers, Wouter Meulemans, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II

Abstract
GPS trajectories of vehicles moving on a road network are a valuable source of traffic information. However, the sheer volume of available data makes it challenging to identify and visualize salient patterns. Meaningful visual summaries of trajectory collections require that both the trajectories and the underlying network are aggregated and simplified in a coherent manner. In this paper we propose a coordinated fully-automated pipeline for computing a schematic overview of mobility patterns from a collection of trajectories on a street network. Our pipeline utilizes well-known building blocks from GIS, automated cartography, and trajectory analysis: map matching, road selection, schematization, movement patterns, and metro-map style rendering. We showcase the results of our pipeline on two real-world trajectory collections around The Hague and Beijing.
Cite as

Bram Custers, Wouter Meulemans, Bettina Speckmann, and Kevin Verbeek. Coordinated Schematization for Visualizing Mobility Patterns on Networks. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{custers_et_al:LIPIcs.GIScience.2021.II.7,
  author =	{Custers, Bram and Meulemans, Wouter and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Coordinated Schematization for Visualizing Mobility Patterns on Networks}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.7},
  URN =		{urn:nbn:de:0030-drops-147665},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.7},
  annote =	{Keywords: Trajectories, Visualization, Schematization}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.8
Harmonious Simplification of Isolines

Authors: Arthur van Goethem, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann

Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II

Abstract
Current techniques for simplification focus on reducing complexity while maintaining the geometric similarity to the input. For isolines that jointly describe a scalar field, however, we postulate that geometric similarity of each isoline separately is not sufficient. Rather, we need to maintain the harmony between these isolines to make them visually relate and describe the structures of the underlying terrain. Based on principles of manual cartography, we propose an algorithm for simplifying isolines while considering harmony explicitly. Our preliminary visual and quantitative results suggest that our algorithm is effective.
Cite as

Arthur van Goethem, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann. Harmonious Simplification of Isolines. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{vangoethem_et_al:LIPIcs.GIScience.2021.II.8,
  author =	{van Goethem, Arthur and Meulemans, Wouter and Reimer, Andreas and Speckmann, Bettina},
  title =	{{Harmonious Simplification of Isolines}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.8},
  URN =		{urn:nbn:de:0030-drops-147675},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.8},
  annote =	{Keywords: Simplification, isolines, harmony}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.56
Obstructing Classification via Projection

Authors: Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jérôme Urhausen, and Kevin Verbeek

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Machine learning and data mining techniques are effective tools to classify large amounts of data. But they tend to preserve any inherent bias in the data, for example, with regards to gender or race. Removing such bias from data or the learned representations is quite challenging. In this paper we study a geometric problem which models a possible approach for bias removal. Our input is a set of points P in Euclidean space ℝ^d and each point is labeled with k binary-valued properties. A priori we assume that it is "easy" to classify the data according to each property. Our goal is to obstruct the classification according to one property by a suitable projection to a lower-dimensional Euclidean space ℝ^m (m < d), while classification according to all other properties remains easy. What it means for classification to be easy depends on the classification model used. We first consider classification by linear separability as employed by support vector machines. We use Kirchberger’s Theorem to show that, under certain conditions, a simple projection to ℝ^{d-1} suffices to eliminate the linear separability of one of the properties whilst maintaining the linear separability of the other properties. We also study the problem of maximizing the linear "inseparability" of the chosen property. Second, we consider more complex forms of separability and prove a connection between the number of projections required to obstruct classification and the Helly-type properties of such separabilities.
Cite as

Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jérôme Urhausen, and Kevin Verbeek. Obstructing Classification via Projection. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 56:1-56:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{haghighatkhah_et_al:LIPIcs.MFCS.2021.56,
  author =	{Haghighatkhah, Pantea and Meulemans, Wouter and Speckmann, Bettina and Urhausen, J\'{e}r\^{o}me and Verbeek, Kevin},
  title =	{{Obstructing Classification via Projection}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{56:1--56:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.56},
  URN =		{urn:nbn:de:0030-drops-144965},
  doi =		{10.4230/LIPIcs.MFCS.2021.56},
  annote =	{Keywords: Projection, classification, models of learning}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.22
Convex Polygons in Cartesian Products

Authors: Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of n real numbers (for short, grid). First, we prove that every such grid contains a convex polygon with Omega(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d in N), and obtain a tight lower bound of Omega(log^{d-1}n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the longest convex polygonal chain in a grid that contains no two points with the same x- or y-coordinate. We show that the maximum size of such a convex polygon can be efficiently approximated up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
Cite as

Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot. Convex Polygons in Cartesian Products. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{decarufel_et_al:LIPIcs.SoCG.2019.22,
  author =	{De Carufel, Jean-Lou and Dumitrescu, Adrian and Meulemans, Wouter and Ophelders, Tim and Pennarun, Claire and T\'{o}th, Csaba D. and Verdonschot, Sander},
  title =	{{Convex Polygons in Cartesian Products}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.22},
  URN =		{urn:nbn:de:0030-drops-104267},
  doi =		{10.4230/LIPIcs.SoCG.2019.22},
  annote =	{Keywords: Erd\H{o}s-Szekeres theorem, Cartesian product, convexity, polyhedron, recursive construction, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.49
Competitive Searching for a Line on a Line Arrangement

Authors: Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We discuss the problem of searching for an unknown line on a known or unknown line arrangement by a searcher S, and show that a search strategy exists that finds the line competitively, that is, with detour factor at most a constant when compared to the situation where S has all knowledge. In the case where S knows all lines but not which one is sought, the strategy is 79-competitive. We also show that it may be necessary to travel on Omega(n) lines to realize a constant competitive ratio. In the case where initially, S does not know any line, but learns about the ones it encounters during the search, we give a 414.2-competitive search strategy.
Cite as

Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans. Competitive Searching for a Line on a Line Arrangement. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 49:1-49:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bouts_et_al:LIPIcs.ISAAC.2018.49,
  author =	{Bouts, Quirijn and Castermans, Thom and van Goethem, Arthur and van Kreveld, Marc and Meulemans, Wouter},
  title =	{{Competitive Searching for a Line on a Line Arrangement}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{49:1--49:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.49},
  URN =		{urn:nbn:de:0030-drops-99970},
  doi =		{10.4230/LIPIcs.ISAAC.2018.49},
  annote =	{Keywords: Competitive searching, line arrangement, detour factor, search strategy}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.23
Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary

Authors: Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Computing optimal deformations between two curves is a fundamental question with various applications, and has recently received much attention in both computational topology and in mathematics in the form of homotopies of disks and annular regions. In this paper, we examine this problem in a geometric setting, where we consider the boundary of a polygonal domain with spikes, point obstacles that can be crossed at an additive cost. We aim to continuously morph from one part of the boundary to another, necessarily passing over all spikes, such that the most expensive intermediate curve is minimized, where the cost of a curve is its geometric length plus the cost of any spikes it crosses. We first investigate the general setting where each spike may have a different cost. For the number of inflection points in an intermediate curve, we present a lower bound that is linear in the number of spikes, even if the domain is convex and the two boundaries for which we seek a morph share an endpoint. We describe a 2-approximation algorithm for the general case, and an optimal algorithm for the case that the two boundaries for which we seek a morph share both endpoints, thereby representing the entire boundary of the domain. We then consider the setting where all spikes have the same unit cost and we describe a polynomial-time exact algorithm. The algorithm combines structural properties of homotopies arising from the geometry with methodology for computing Fréchet distances.
Cite as

Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann. Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.ESA.2017.23,
  author =	{Burton, Benjamin and Chambers, Erin and van Kreveld, Marc and Meulemans, Wouter and Ophelders, Tim and Speckmann, Bettina},
  title =	{{Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.23},
  URN =		{urn:nbn:de:0030-drops-78630},
  doi =		{10.4230/LIPIcs.ESA.2017.23},
  annote =	{Keywords: Fr\'{e}chet distance, polygonal domain, homotopy, geodesic, obstacle}
}
Document
Multimedia Contribution
DOI: 10.4230/LIPIcs.SoCG.2017.64
Folding Free-Space Diagrams: Computing the Fréchet Distance between 1-Dimensional Curves (Multimedia Contribution)

Authors: Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, and Taichi Shiitada

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
By folding the free-space diagram for efficient preprocessing, we show that the Frechet distance between 1D curves can be computed in O(nk log n) time, assuming one curve has ply k.
Cite as

Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, and Taichi Shiitada. Folding Free-Space Diagrams: Computing the Fréchet Distance between 1-Dimensional Curves (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 64:1-64:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2017.64,
  author =	{Buchin, Kevin and Chun, Jinhee and L\"{o}ffler, Maarten and Markovic, Aleksandar and Meulemans, Wouter and Okamoto, Yoshio and Shiitada, Taichi},
  title =	{{Folding Free-Space Diagrams: Computing the Fr\'{e}chet Distance between 1-Dimensional Curves}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{64:1--64:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.64},
  URN =		{urn:nbn:de:0030-drops-72417},
  doi =		{10.4230/LIPIcs.SoCG.2017.64},
  annote =	{Keywords: Frechet distance, ply, k-packed curves}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.22
Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance

Authors: Quirijn W. Bouts, Irina Irina Kostitsyna, Marc van Kreveld, Wouter Meulemans, Willem Sonke, and Kevin Verbeek

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We show how to represent a simple polygon P by a (pixel-based) grid polygon Q that is simple and whose Hausdorff or Fréchet distance to P is small. For any simple polygon P, a grid polygon exists with constant Hausdorff distance between their boundaries and their interiors. Moreover, we show that with a realistic input assumption we can also realize constant Fréchet distance between the boundaries. We present algorithms accompanying these constructions, heuristics to improve their output while keeping the distance bounds, and experiments to assess the output.
Cite as

Quirijn W. Bouts, Irina Irina Kostitsyna, Marc van Kreveld, Wouter Meulemans, Willem Sonke, and Kevin Verbeek. Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bouts_et_al:LIPIcs.ESA.2016.22,
  author =	{Bouts, Quirijn W. and Irina Kostitsyna, Irina and van Kreveld, Marc and Meulemans, Wouter and Sonke, Willem and Verbeek, Kevin},
  title =	{{Mapping Polygons to the Grid with Small Hausdorff and Fr\'{e}chet Distance}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.22},
  URN =		{urn:nbn:de:0030-drops-63738},
  doi =		{10.4230/LIPIcs.ESA.2016.22},
  annote =	{Keywords: grid mapping, Hausdorff distance, Fr\'{e}chet distance, digital geometry}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact