Publications

Please note that in theoretical computer science and mathematics the author order is purely alphabetical. However, due to the cross-disciplinary nature of my research, some papers appeared at venues or in journals with other conventions.

Other aggregations of my publications include Google scholar and DBLP. My ORCID is (very) incomplete.

Sort by year, then publication type, then title Sort by publication type, then year, then title Sort by title Reset

• Chapters in Books
• Journals
• Formally Reviewed Conference Proceedings
• Weakly Refereed Conference Proceedings and Workshop Abstracts
• Theses

2023

• Data-Spatial Layouts for Grid Maps
  Nathan van Beusekom, Wouter Meulemans, Bettina Speckmann, and Jo Wood.
  12th International Conference on Geographic Information Science (GIScience 2023), pp. 10:1—10:17, 2023.
  
  － Abstract
  

  <p>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.</p>

  － BibTeX
  

  @article{data-spatial-layouts-for-grid-maps:2023,
      title = {Data-Spatial Layouts for Grid Maps},
      author = {Nathan van Beusekom and Wouter Meulemans and Bettina Speckmann and Jo Wood},
      year = {2023},
      bookTitle = {12th International Conference on Geographic Information Science (GIScience 2023)},
  }
  

• Graph Drawing Contest Report
  Philipp Kindermann, Fabian Klute, Tamara Mchedlidze, and Wouter Meulemans.
  Proceedings of the International Symposium on Graph Drawing and Network Visualization, pp. 459—470, 2023.
  
  － Abstract
  

  <p>This report describes the 29th Annual Graph Drawing Contest, held in conjunction with the 30th International Symposium on Graph Drawing and Network Visualization (GD’22) in Tokyo, Japan. Due to the continuing global COVID-19 pandemic, the conference and thus also the contest was held in a hybrid format, with both on-site and online participants. The mission of the Graph Drawing Contest is to monitor and challenge the current state of the art in graph-drawing technology.</p>

  － BibTeX
  

  @article{graph-drawing-contest-report:2023,
      title = {Graph Drawing Contest Report},
      author = {Philipp Kindermann and Fabian Klute and Tamara Mchedlidze and Wouter Meulemans},
      year = {2023},
      bookTitle = {Proceedings of the International Symposium on Graph Drawing and Network Visualization},
  }
  

2022

• Computing Schematic Layouts for Spatial Hypergraphs on Concentric Circles and Grids
  M.A. Bekos, D.J.C. Dekker, F. Frank, W. Meulemans, P. Rodgers, André Schulz, and S. Wessel.
  Computer Graphics Forum, 41(6):316—335, 2022.
  
  － Abstract
  

  <br/>

  － BibTeX
  

  @article{computing-schematic-layouts-for-spatial-hypergraphs-on-concentric-circles-and-grids:2022,
      title = {Computing Schematic Layouts for Spatial Hypergraphs on Concentric Circles and Grids},
      author = {M.A. Bekos and D.J.C. Dekker and F. Frank and W. Meulemans and P. Rodgers and André Schulz and S. Wessel},
      year = {2022},
      bookTitle = {Computer Graphics Forum},
  }
  

  [ PDF ]
  
• Multicriteria Optimization for Dynamic Demers Cartograms
  Soeren Nickel, Max Sondag, Wouter Meulemans, Stephen G. Kobourov, Jaakko Peltonen, and Martin Nöllenburg.
  IEEE Transactions on Visualization and Computer Graphics, 28(6):2376—2387, 2022.
  
  － Abstract
  

  Cartograms are popular for visualizing numerical data for administrative regions in thematic maps. When there are multiple data values per region (over time or from different datasets) shown as animated or juxtaposed cartograms, preserving the viewer’s mental map in terms of stability between multiple cartograms is another important criterion alongside traditional cartogram criteria such as maintaining adjacencies. We present a method to compute stable stable Demers cartograms, where each region is shown as a square scaled proportionally to the given numerical data and similar data yield similar cartograms. We enforce orthogonal separation constraints using linear programming, and measure quality in terms of keeping adjacent regions close (cartogram quality) and using similar positions for a region between the different data values (stability). Our method guarantees the ability to connect most lost adjacencies with minimal-length planar orthogonal polylines. Experiments show that our method yields good quality and stability on multiple quality criteria.

  － BibTeX
  

  @article{multicriteria-optimization-for-dynamic-demers-cartograms:2022,
      title = {Multicriteria Optimization for Dynamic Demers Cartograms},
      author = {Soeren Nickel and Max Sondag and Wouter Meulemans and Stephen G. Kobourov and Jaakko Peltonen and Martin Nöllenburg},
      year = {2022},
      bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
  }
  

  [ PDF ]
  
• Obstructing Classification Via Projection
  Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jérôme Urhausen, and Kevin A.B. Verbeek.
  Computing in Geometry and Topology, 1(1):2:1—2:21, 2022.
  
  － 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 R^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 R^m (m &lt; d), while classification according to all other properties remains easy.<br/><br/>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 R^(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.<br/>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.

  － BibTeX
  

  @article{obstructing-classification-via-projection:2022,
      title = {Obstructing Classification Via Projection},
      author = {Pantea Haghighatkhah and Wouter Meulemans and Bettina Speckmann and Jérôme Urhausen and Kevin A.B. Verbeek},
      year = {2022},
      bookTitle = {Computing in Geometry and Topology},
  }
  

  [ PDF ]
  
• Simultaneous Matrix Orderings for Graph Collections
  Nathan van Beusekom, Wouter Meulemans, and Bettina Speckmann.
  IEEE Transactions on Visualization and Computer Graphics, 28(1):1—10, 2022.
  
  － Abstract
  

  Undirected graphs are frequently used to model phenomena that deal with interacting objects, such as social networks, brain activity and communication networks. The topology of an undirected graph G can be captured by an adjacency matrix; this matrix in turn can be visualized directly to give insight into the graph structure. Which visual patterns appear in such a matrix visualization crucially depends on the ordering of its rows and columns. Formally defining the quality of an ordering and then automatically computing a high-quality ordering are both challenging problems; however, effective heuristics exist and are used in practice.<br/><br/>Often, graphs do not exist in isolation but as part of a collection of graphs on the same set of vertices, for example, brain scans over time or of different people.<br/>To visualize such graph collections, we need a single ordering that works well for all matrices simultaneously.<br/>The current state-of-the-art solves this problem by taking a (weighted) union over all graphs and applying existing heuristics. However, this union leads to a loss of information, specifically in those parts of the graphs which are different. <br/>We propose a collection-aware approach to avoid this loss of information and apply it to two popular heuristic methods: leaf order and barycenter.<br/><br/>The de-facto standard computational quality metrics for matrix ordering capture only block-diagonal patterns (cliques). Instead, we propose to use Moran's I, a spatial auto-correlation metric, which captures the full range of established patterns. Moran's I refines previously proposed stress measures. Furthermore, the popular leaf order method heuristically optimizes a similar measure which further supports the use of Moran's I in this context. An ordering that maximizes Moran's I can be computed via solutions to the Traveling Salesperson Problem (TSP); orderings that approximate the optimal ordering can be computed more efficiently, using any of the approximation algorithms for metric TSP.<br/><br/>We evaluated our methods for simultaneous orderings on real-world datasets using Moran's I as the quality metric. Our results show that our collection-aware approach matches or improves performance<br/>compared to the union approach, depending on the similarity of the graphs in the collection. <br/>Specifically, our Moran's I-based collection-aware leaf order implementation consistently outperforms other implementations.<br/>Our collection-aware implementations carry no significant additional computational costs.

  － BibTeX
  

  @article{simultaneous-matrix-orderings-for-graph-collections:2022,
      title = {Simultaneous Matrix Orderings for Graph Collections},
      author = {Nathan van Beusekom and Wouter Meulemans and Bettina Speckmann},
      year = {2022},
      bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
  }
  

  [ PDF ]
  
• Physically Consistent Map Matching
  Bram A. Custers, Wouter Meulemans, Marcel J.M. Roeloffzen, Bettina Speckmann, and Kevin A.B. Verbeek.
  Physically Consistent Map Matching, 2022.
  
  － BibTeX
  

  @article{physically-consistent-map-matching:2022,
      title = {Physically Consistent Map Matching},
      author = {Bram A. Custers and Wouter Meulemans and Marcel J.M. Roeloffzen and Bettina Speckmann and Kevin A.B. Verbeek},
      year = {2022},
      bookTitle = {Physically Consistent Map Matching},
  }
  

  [ PDF ]
  

2021

• A Simple Pipeline for Coherent Grid Maps
  Wouter Meulemans, Max F.M. Sondag, and Bettina Speckmann.
  IEEE Transactions on Visualization and Computer Graphics, 27(2):1236—1246, 2021.
  
  － Abstract
  

  Grid maps are spatial arrangements of simple tiles (often squares or hexagons), each of which represents a spatial element. They are an established, effective way to show complex data per spatial element, using visual encodings within each tile ranging from simple coloring to nested small-multiples visualizations. An effective grid map is coherent with the underlying geographic space: the tiles maintain the contiguity, neighborhoods and identifiability of the corresponding spatial elements, while the grid map as a whole maintains the global shape of the input. Of particular importance are salient local features of the global shape which need to be represented by tiles assigned to the appropriate spatial elements. State-of-the-art techniques can adequately deal only with simple cases, such as close-to-uniform spatial distributions or global shapes that have few characteristic features. We introduce a simple fully-automated 3-step pipeline for computing coherent grid maps. Each step is a well-studied problem: shape decomposition based on salient features, tile-based Mosaic Cartograms, and point-set matching. Our pipeline is a seamless composition of existing techniques for these problems and results in high-quality grid maps. We provide an implementation, demonstrate the efficacy of our approach on various complex datasets, and compare it to the state-of-the-art.

  － BibTeX
  

  @article{a-simple-pipeline-for-coherent-grid-maps:2021,
      title = {A Simple Pipeline for Coherent Grid Maps},
      author = {Wouter Meulemans and Max F.M. Sondag and Bettina Speckmann},
      year = {2021},
      bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
  }
  

  [ PDF ]
  [ PDF ]
  
• Convex Polygons in Cartesian Products
  Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot.
  Journal of Computational Geometry, 11(2):205—233, 2021.
  
  － Abstract
  

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

  － BibTeX
  

  @article{convex-polygons-in-cartesian-products:2021,
      title = {Convex Polygons in Cartesian Products},
      author = {Jean-Lou De Carufel and Adrian Dumitrescu and Wouter Meulemans and Tim Ophelders and Claire Pennarun and Csaba D. Tóth and Sander Verdonschot},
      year = {2021},
      bookTitle = {Journal of Computational Geometry},
  }
  

  [ PDF ]
  
• Maximum Physically Consistent Trajectories
  Bram A. Custers, Frank Staals, Bettina Speckmann, Wouter Meulemans, and Mees van de Kerkhof.
  ACM Transactions on Spatial Algorithms and Systems , 7(4):, 2021.
  
  － Abstract
  

  Trajectories are usually collected with physical sensors, which are prone to errors and cause outliers in the data. We aim to identify such outliers via the physical properties of the tracked entity, that is, we consider its physical possibility to visit combinations of measurements. We describe optimal algorithms to compute maximum subsequences of measurements that are consistent with (simplified) physics models. Our results are output-sensitive with respect to the number k of outliers in a trajectory of n measurements. Specifically, we describe an O(n log n log2 k)-time algorithm for 2D trajectories using a model with unbounded acceleration but bounded velocity, and an O(nk)-time algorithm for any model where consistency is “concatenable”: a consistent subsequence that ends where another begins together form a consistent sequence. We also consider acceleration-bounded models that are not concatenable. We show how to compute the maximum subsequence for such models in O(n k2 log k) time, under appropriate realism conditions. Finally, we experimentally explore the performance of our algorithms on several large real-world sets of trajectories. Our experiments show that we are generally able to retain larger fractions of noisy trajectories than previous work and simpler greedy approaches. We also observe that the speed-bounded model may in practice approximate the acceleration-bounded model quite well, though we observed some variation between datasets.

  － BibTeX
  

  @article{maximum-physically-consistent-trajectories:2021,
      title = {Maximum Physically Consistent Trajectories},
      author = {Bram A. Custers and Frank Staals and Bettina Speckmann and Wouter Meulemans and Mees van de Kerkhof},
      year = {2021},
      bookTitle = {ACM Transactions on Spatial Algorithms and Systems },
  }
  

  [ PDF ]
  
• Topological Stability of Kinetic k-Centers
  Ivor van der Hoog, Marc J. van Kreveld, Wouter Meulemans, Kevin Verbeek, and Jules Wulms.
  Theoretical Computer Science, 866:145—159, 2021.
  
  － Abstract
  

  <p>We study the k-center problem in a kinetic setting: given a set of continuously moving points P in the plane, determine a set of k (moving) disks that cover P at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model allows positive results only for k&lt;3. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of k-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove upper and lower bounds on the ratio between the radii of an optimal but unstable solution and the radii of a topologically stable solution—the topological stability ratio—considering various metrics and various optimization criteria. For k=2 we provide tight bounds, and for small k&gt;2 we can obtain nontrivial lower and upper bounds. Finally, we provide an algorithm to compute the topological stability ratio in polynomial time for constant k.</p>

  － BibTeX
  

  @article{topological-stability-of-kinetic-k-centers:2021,
      title = {Topological Stability of Kinetic k-Centers},
      author = {Ivor van der Hoog and Marc J. van Kreveld and Wouter Meulemans and Kevin Verbeek and Jules Wulms},
      year = {2021},
      bookTitle = {Theoretical Computer Science},
  }
  

  [ PDF ]
  [ PDF ]
  
• Coordinated Schematization for Visualizing Mobility Patterns on Networks
  Bram A. Custers, Wouter Meulemans, Bettina Speckmann, and Kevin Verbeek.
  11th International Conference on Geographic Information Science - Part II, GIScience 2021, pp. VII, 2021.
  
  － Abstract
  

  <p>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.</p>

  － BibTeX
  

  @article{coordinated-schematization-for-visualizing-mobility-patterns-on-networks:2021,
      title = {Coordinated Schematization for Visualizing Mobility Patterns on Networks},
      author = {Bram A. Custers and Wouter Meulemans and Bettina Speckmann and Kevin Verbeek},
      year = {2021},
      bookTitle = {11th International Conference on Geographic Information Science - Part II, GIScience 2021},
  }
  

• Graph Drawing Contest Report
  Philipp Kindermann, Tamara Mchedlidze, and Wouter Meulemans.
  Proceedings of the International Symposium on Graph Drawing and Network Visualization, pp. 409—417, 2021.
  
  － Abstract
  

  <p>This report describes the 28th Annual Graph Drawing Contest, held in conjunction with the 29th International Symposium on Graph Drawing and Network Visualization (GD’21) in Tübingen, Germany. Due to the global COVID-19 pandemic, the conference and thus also the contest was held in a hybrid format, with both on-site and online participants. The mission of the Graph Drawing Contest is to monitor and challenge the current state of the art in graph-drawing technology.</p>

  － BibTeX
  

  @article{graph-drawing-contest-report:2021,
      title = {Graph Drawing Contest Report},
      author = {Philipp Kindermann and Tamara Mchedlidze and Wouter Meulemans},
      year = {2021},
      bookTitle = {Proceedings of the International Symposium on Graph Drawing and Network Visualization},
  }
  

• Harmonious Simplification of Isolines
  Arthur van Goethem, Wouter Meulemans, Andreas W. Reimer, and Bettina Speckmann.
  Proceedings of the 11th International Conference on Geographic Information Science, pp. 8:1—8:16, 2021.
  
  － Abstract
  

  <p>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.</p>

  － BibTeX
  

  @article{harmonious-simplification-of-isolines:2021,
      title = {Harmonious Simplification of Isolines},
      author = {Arthur van Goethem and Wouter Meulemans and Andreas W. Reimer and Bettina Speckmann},
      year = {2021},
      bookTitle = {Proceedings of the 11th International Conference on Geographic Information Science},
  }
  

• Obstructing Classification Via Projection
  Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jérôme Urhausen, and Kevin Verbeek.
  46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, 2021.
  
  － Abstract
  

  <p>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 Rd 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 Rm (m &lt; 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 Rd1 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. </p>

  － BibTeX
  

  @article{obstructing-classification-via-projection:2021,
      title = {Obstructing Classification Via Projection},
      author = {Pantea Haghighatkhah and Wouter Meulemans and Bettina Speckmann and Jérôme Urhausen and Kevin Verbeek},
      year = {2021},
      bookTitle = {46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021},
  }
  

• Route Reconstruction from Traffic Flow Via Representative Trajectories
  Bram A. Custers, Kevin A.B. Verbeek, Wouter Meulemans, and Bettina Speckmann.
  Proc. 29th International Conference on Advances in Geographic Information (SIGSPATIAL), pp. 41—52, 2021.
  
  － Abstract
  

  Understanding human mobility patterns is an important aspect of traffic analysis and urban planning. Trajectory data provide detailed views on specific routes, but typically do not capture all traffic. On the other hand, loop detectors built into the road network capture all traffic flow at specific locations, but provide no information on the individual routes. Given a set of loop-detector measurements as well as a (small) set of representative trajectories, our goal is to investigate how one can effectively combine these two partial data sources to create a more complete picture of the underlying mobility patterns. Specifically, we want to reconstruct a realistic set of routes from the loop-detector data, using the given trajectories as representatives of typical behavior.<br/><br/>We model the loop-detector data as a network flow field that needs to be covered by the reconstructed routes and we capture the realism of the routes via the strong Fréchet distance to the representative trajectories. We prove that several forms of the resulting algorithmic problem are NP-hard. Hence we explore heuristic approaches which decompose the flow well while following the representative trajectories to varying degrees. We propose an iterative Fréchet Routes (FR) heuristic which generates candidates routes with bounded Fréchet distance to the representative trajectories. We also describe a variant of multi-commodity min-cost flow (MCMCF) which is only loosely coupled to the trajectories.<br/><br/>We perform an extensive experimental evaluation of our two proposed approaches in comparison to a global min-cost flow (GMCF), which is essentially agnostic to the representative trajectories. To make meaningful claims in terms of quality, we derive a ground truth by map-matching real-world trajectories. We find that GMCF explains the flow best, but produces a large number of often nonsensical routes (significantly more than the ground truth). MCMCF produces a large number of mostly realistic routes which explain the flow reasonably well. In contrast, FR produces much smaller sets of realistic routes which still explain the flow well, at the cost of a higher running time. Finally, we report on the results of a case study which combines real-world loop detector data and representative trajectories for the region around The Hague, the Netherlands.<br/>

  － BibTeX
  

  @article{route-reconstruction-from-traffic-flow-via-representative-trajectories:2021,
      title = {Route Reconstruction from Traffic Flow Via Representative Trajectories},
      author = {Bram A. Custers and Kevin A.B. Verbeek and Wouter Meulemans and Bettina Speckmann},
      year = {2021},
      bookTitle = {Proc. 29th International Conference on Advances in Geographic Information (SIGSPATIAL)},
  }
  

  [ PDF lock ]
  
• Stable Visual Summaries for Trajectory Collections
  Jules Wulms, Juri Buchmuller, Wouter Meulemans, Kevin Verbeek, and Bettina Speckmann.
  Proceedings - 2021 IEEE 14th Pacific Visualization Symposium, PacificVis 2021, pp. 61—70, 2021.
  
  － Abstract
  

  <p>The availability of devices that track moving objects has led to an explosive growth in trajectory data. When exploring the resulting large trajectory collections, visual summaries are a useful tool to identify time intervals of interest. A typical approach is to represent the spatial positions of the tracked objects at each time step via a one-dimensional ordering; visualizations of such orderings can then be placed in temporal order along a time line. There are two main criteria to assess the quality of the resulting visual summary: spatial quality - how well does the ordering capture the structure of the data at each time step, and stability - how coherent are the orderings over consecutive time steps or temporal ranges?In this paper we introduce a new Stable Principal Component (SPC) method to compute such orderings, which is explicitly parameterized for stability, allowing a trade-off between the spatial quality and stability. We conduct extensive computational experiments that quantitatively compare the orderings produced by ours and other stable dimensionality-reduction methods to various state-of-the-art approaches using a set of well-established quality metrics that capture spatial quality and stability. We conclude that stable dimensionality reduction outperforms existing methods on stability, without sacrificing spatial quality or efficiency; in particular, our new SPC method does so at a fraction of the computational costs.</p>

  － BibTeX
  

  @article{stable-visual-summaries-for-trajectory-collections:2021,
      title = {Stable Visual Summaries for Trajectory Collections},
      author = {Jules Wulms and Juri Buchmuller and Wouter Meulemans and Kevin Verbeek and Bettina Speckmann},
      year = {2021},
      bookTitle = {Proceedings - 2021 IEEE 14th Pacific Visualization Symposium, PacificVis 2021},
  }
  

• Near-Delaunay Metrics
  Nathan van Beusekom, Kevin A. Buchin, Hidde O. Koerts, Wouter Meulemans, Benjamin Rodatz, and Bettina Speckmann.
  pp. 1—11, 2021.
  
  － Abstract
  

  We study metrics that assess how close a triangulation is to being a Delaunay triangulation, for use in contexts where a good triangulation is desired but constraints (e.g., maximum degree) prevent the use of the Delaunay triangulation itself. Our near-Delaunay metrics derive from common Delaunay properties and satisfy a basic set of design criteria, such as being invariant under similarity transformations. We compare the metrics, showing that each can make different judgments as to which triangulation is closer to Delaunay. We also present a preliminary experiment, showing how optimizing for these metrics under different constraints gives similar, but not necessarily identical results, on random and constructed small point sets.

  － BibTeX
  

  @article{near-delaunay-metrics:2021,
      title = {Near-Delaunay Metrics},
      author = {Nathan van Beusekom and Kevin A. Buchin and Hidde O. Koerts and Wouter Meulemans and Benjamin Rodatz and Bettina Speckmann},
      year = {2021},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Route Reconstruction from Traffic Flow Via Representative Trajectories
  Bram A. Custers, Bettina Speckmann, Wouter Meulemans, and Kevin A.B. Verbeek.
  2021.
  
  － BibTeX
  

  @article{route-reconstruction-from-traffic-flow-via-representative-trajectories:2021,
      title = {Route Reconstruction from Traffic Flow Via Representative Trajectories},
      author = {Bram A. Custers and Bettina Speckmann and Wouter Meulemans and Kevin A.B. Verbeek},
      year = {2021},
      bookTitle = {},
  }
  

2020

• Can Real Social Epistemic Networks Deliver the Wisdom of Crowds?
  Emily Sullivan, Max Sondag, Ignaz Rutter, Wouter Meulemans, Scott Cunningham, Bettina Speckmann, and Mark Alfano.
  Oxford Studies in Experimental Philosophy, Volume 3, pp. 29—63, 2020.
  
  － BibTeX
  

  @article{can-real-social-epistemic-networks-deliver-the-wisdom-of-crowds-:2020,
      title = {Can Real Social Epistemic Networks Deliver the Wisdom of Crowds?},
      author = {Emily Sullivan and Max Sondag and Ignaz Rutter and Wouter Meulemans and Scott Cunningham and Bettina Speckmann and Mark Alfano},
      year = {2020},
      bookTitle = {Oxford Studies in Experimental Philosophy, Volume 3},
  }
  

• Vulnerability in Social Epistemic Networks
  Emily Sullivan, Max Sondag, Ignaz Rutter, Wouter Meulemans, Scott Cunningham, Bettina Speckmann, and Mark Alfano.
  International Journal of Philosophical Studies, 28(5):731—753, 2020.
  
  － Abstract
  

  <p>Social epistemologists should be well-equipped to explain and evaluate the growing vulnerabilities associated with filter bubbles, echo chambers, and group polarization in social media. However, almost all social epistemology has been built for social contexts that involve merely a speaker-hearer dyad. Filter bubbles, echo chambers, and group polarization all presuppose much larger and more complex network structures. In this paper, we lay the groundwork for a properly social epistemology that gives the role and structure of networks their due. In particular, we formally define epistemic constructs that quantify the structural epistemic position of each node within an interconnected network. We argue for the epistemic value of a structure that we call the (m,k)-observer. We then present empirical evidence that (m,k)-observers are rare in social media discussions of controversial topics, which suggests that people suffer from serious problems of epistemic vulnerability. We conclude by arguing that social epistemologists and computer scientists should work together to develop minimal interventions that improve the structure of epistemic networks.</p>

  － BibTeX
  

  @article{vulnerability-in-social-epistemic-networks:2020,
      title = {Vulnerability in Social Epistemic Networks},
      author = {Emily Sullivan and Max Sondag and Ignaz Rutter and Wouter Meulemans and Scott Cunningham and Bettina Speckmann and Mark Alfano},
      year = {2020},
      bookTitle = {International Journal of Philosophical Studies},
  }
  

  [ PDF ]
  
• Graph Drawing Contest Report
  Philipp Kindermann, Tamara Mchedlidze, Wouter Meulemans, and Ignaz Rutter.
  Proceedings of the International Symposium on Graph Drawing and Network Visualization, pp. 507—519, 2020.
  
  － Abstract
  

  <p>This report describes the 27th Annual Graph Drawing Contest, held in conjunction with the 28th International Symposium on Graph Drawing and Network Visualization (GD’20) in Vancouver, BC, Canada. Due to the global COVID-19 pandemic, the contest was held completely online. The mission of the Graph Drawing Contest is to monitor and challenge the current state of the art in graph-drawing technology.</p>

  － BibTeX
  

  @article{graph-drawing-contest-report:2020,
      title = {Graph Drawing Contest Report},
      author = {Philipp Kindermann and Tamara Mchedlidze and Wouter Meulemans and Ignaz Rutter},
      year = {2020},
      bookTitle = {Proceedings of the International Symposium on Graph Drawing and Network Visualization},
  }
  

• Simplification with Parallelism
  Arthur I. van Goethem, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann.
  Abstr. 23rd ICA Workshop on Generalisation and Multiple Representation, 2020.
  
  － BibTeX
  

  @article{simplification-with-parallelism:2020,
      title = {Simplification with Parallelism},
      author = {Arthur I. van Goethem and Wouter Meulemans and Andreas Reimer and Bettina Speckmann},
      year = {2020},
      bookTitle = {Abstr. 23rd ICA Workshop on Generalisation and Multiple Representation},
  }
  

• Uncertainty Treemaps
  Max Sondag, Wouter Meulemans, Christoph Schulz, Kevin Verbeek, Daniel Weiskopf, and Bettina Speckmann.
  2020 IEEE Pacific Visualization Symposium, PacificVis 2020 - Proceedings, pp. 111—120, 2020.
  
  － Abstract
  

  <p>Rectangular treemaps visualize hierarchical numerical data by recursively partitioning an input rectangle into smaller rectangles whose areas match the data. Numerical data often has uncertainty associated with it. To visualize uncertainty in a rectangular treemap, we identify two conflicting key requirements: (i) to assess the data value of a node in the hierarchy, the area of its rectangle should directly match its data value, and (ii) to facilitate comparison between data and uncertainty, uncertainty should be encoded using the same visual variable as the data, that is, area. We present Uncertainty Treemaps, which meet both requirements simultaneously by introducing the concept of hierarchical uncertainty masks. First, we define a new cost function that measures the quality of Uncertainty Treemaps. Then, we show how to adapt existing treemapping algorithms to support uncertainty masks. Finally, we demonstrate the usefulness and quality of our technique through an expert review and a computational experiment on real-world datasets.</p>

  － BibTeX
  

  @article{uncertainty-treemaps:2020,
      title = {Uncertainty Treemaps},
      author = {Max Sondag and Wouter Meulemans and Christoph Schulz and Kevin Verbeek and Daniel Weiskopf and Bettina Speckmann},
      year = {2020},
      bookTitle = {2020 IEEE Pacific Visualization Symposium, PacificVis 2020 - Proceedings},
  }
  

  [ PDF ]
  
• Orthogonal Schematization with Minimum Homotopy Area
  Bram A. Custers, Kevin A.B. Verbeek, Bettina Speckmann, Wouter Meulemans, Irina Kostitsyna, and Jeff Erickson.
  2020.
  
  － BibTeX
  

  @article{orthogonal-schematization-with-minimum-homotopy-area:2020,
      title = {Orthogonal Schematization with Minimum Homotopy Area},
      author = {Bram A. Custers and Kevin A.B. Verbeek and Bettina Speckmann and Wouter Meulemans and Irina Kostitsyna and Jeff Erickson},
      year = {2020},
      bookTitle = {},
  }
  

2019

• Efficient Optimal Overlap Removal
  W. Meulemans.
  Computer Graphics Forum, 38(3):713—723, 2019.
  
  － Abstract
  

  <p>Motivated by visualizing spatial data using proportional symbols, we study the following problem: given a set of overlapping squares of varying sizes, minimally displace the squares as to remove the overlap while maintaining the orthogonal order on their centers. Though this problem is NP-hard, we show that rotating the squares by 45 degrees into diamonds allows for a linear or convex quadratic program. It is thus efficiently solvable even for relatively large instances. This positive result and the flexibility offered by constraint programming allow us to study various trade-offs for overlap removal. Specifically, we model and evaluate through computational experiments the relations between displacement, scale and order constraints for static data, and between displacement and temporal coherence for time-varying data. Finally, we also explore the generalization of our methodology to other shapes.</p>

  － BibTeX
  

  @article{efficient-optimal-overlap-removal:2019,
      title = {Efficient Optimal Overlap Removal},
      author = {W. Meulemans},
      year = {2019},
      bookTitle = {Computer Graphics Forum},
  }
  

  [ PDF ]
  
• Geometry and Generation of a New Graph Planarity Game
  Rutger Kraaijer, Marc J. van Kreveld, Wouter Meulemans, and André van Renssen.
  Journal of Graph Algorithms and Applications, 23(4):603—624, 2019.
  
  － Abstract
  

  <p>We introduce a new abstract graph game, Swap Planarity, where the goal is to reach a state without edge intersections and a move consists of swapping the locations of two vertices connected by an edge. We analyze this puzzle game using concepts from graph theory and graph drawing, computational geometry, and complexity. Furthermore, we specify quality criteria for puzzle instances, and describe a method to generate high-quality instances. We also report on experiments that show how well this generation process works.</p>

  － BibTeX
  

  @article{geometry-and-generation-of-a-new-graph-planarity-game:2019,
      title = {Geometry and Generation of a New Graph Planarity Game},
      author = {Rutger Kraaijer and Marc J. van Kreveld and Wouter Meulemans and André van Renssen},
      year = {2019},
      bookTitle = {Journal of Graph Algorithms and Applications},
  }
  

  [ PDF ]
  
• Locally Correct Fréchet Matchings
  Kevin Buchin, Maike Buchin, Wouter Meulemans, and Bettina Speckmann.
  Computational Geometry, 76:1—18, 2019.
  
  － Abstract
  

  <p>The Fréchet distance is a metric to compare two curves, which is based on monotone matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to “natural” matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such matching exists for two polygonal curves and give an O(N³log⁡N) algorithm to compute it, where N is the number of edges in both curves. We also present an O(N²) algorithm to compute a locally correct discrete Fréchet matching.</p>

  － BibTeX
  

  @article{locally-correct-fr-chet-matchings:2019,
      title = {Locally Correct Fréchet Matchings},
      author = {Kevin Buchin and Maike Buchin and Wouter Meulemans and Bettina Speckmann},
      year = {2019},
      bookTitle = {Computational Geometry},
  }
  

  [ PDF ]
  
• Short Plane Supports for Spatial Hypergraphs
  Thom H.A. Castermans, Mereke van Garderen, Wouter Meulemans, Martin Nöllenburg, and Xiaoru Yuan.
  Journal of Graph Algorithms and Applications, 23(3):463—498, 2019.
  
  － Abstract
  

  <p>A graph G = (V,E) is a support of a hypergraph H = (V,S) if every hyperedge induces a connected subgraph in G. Supports are used for certain types of hypergraph visualizations. In this paper we consider visualizing spatial hypergraphs, where each vertex has a fixed location in the plane. This is the case, e.g., when modeling set systems of geospatial locations as hypergraphs. By applying established aesthetic quality criteria we are interested in finding supports that yield plane straight-line drawings with minimum total edge length on the input point set V. We first show, from a theoretical point of view, that the problem is NP-hard already under rather mild conditions as well as a negative approximability results. Therefore, the main focus of the paper lies on practical heuristic algorithms as well as an exact, ILP-based approach for computing short plane supports. We report results from computational experiments that investigate the effect of requiring planarity and acyclicity on the resulting support length. Further, we evaluate the performance and trade-offs between solution quality and speed of several heuristics relative to each other and compared to optimal solutions.</p>

  － BibTeX
  

  @article{short-plane-supports-for-spatial-hypergraphs:2019,
      title = {Short Plane Supports for Spatial Hypergraphs},
      author = {Thom H.A. Castermans and Mereke van Garderen and Wouter Meulemans and Martin Nöllenburg and Xiaoru Yuan},
      year = {2019},
      bookTitle = {Journal of Graph Algorithms and Applications},
  }
  

  [ PDF ]
  
• Spatially and Temporally Coherent Visual Summaries
  Jules J.H.M. Wulms, Juri Buchmüller, Wouter Meulemans, Kevin A.B. Verbeek, and Bettina Speckmann.
  arXiv, 2019:, 2019.
  
  － Abstract
  

  When exploring large time-varying data sets, visual summaries are a useful tool to identify time intervals of interest for further consideration. A typical approach is to represent the data elements at each time step in a compact one-dimensional form or via a one-dimensional ordering. Such 1D representations can then be placed in temporal order along a time line. There are two main criteria to assess the quality of the resulting visual summary: spatial quality -- how well does the 1D representation capture the structure of the data at each time step, and stability -- how coherent are the 1D representations over consecutive time steps or temporal ranges? We focus on techniques that create such visual summaries using 1D orderings for entities moving in 2D. We introduce stable techniques based on well-established dimensionality-reduction techniques: Principle Component Analysis, Sammon mapping, and t-SNE. Our Stable Principal Component method is explicitly parametrized for stability, allowing a trade-off between the two quality criteria. We conduct computational experiments that compare our stable methods to various state-of-the-art approaches using a set of well-established quality metrics that capture the two main criteria. These experiments demonstrate that our stable algorithms outperform existing methods on stability, without sacrificing spatial quality or efficiency.

  － BibTeX
  

  @article{spatially-and-temporally-coherent-visual-summaries:2019,
      title = {Spatially and Temporally Coherent Visual Summaries},
      author = {Jules J.H.M. Wulms and Juri Buchmüller and Wouter Meulemans and Kevin A.B. Verbeek and Bettina Speckmann},
      year = {2019},
      bookTitle = {arXiv},
  }
  

  [ PDF ]
  
• Stability Analysis of Kinetic Orientation-Based Shape Descriptors
  Wouter Meulemans, Kevin Verbeek, and Jules Wulms.
  arXiv, 2019:, 2019.
  
  － Abstract
  

  We study three orientation-based shape descriptors on a set of continuously moving points P: the first principal component, the smallest oriented bounding box and the thinnest strip. Each of these shape descriptors essentially defines a cost capturing the quality of the descriptor (sum of squared distances for principal component, area for oriented bounding box, and width for strip), and uses the orientation that minimizes the cost. This optimal orientation may be very unstable as the points are moving, which is undesirable in many practical scenarios. Alternatively, we can bound the speed with which the orientation of the descriptor may change. However, this can increase the cost (and hence lower the quality) of the resulting shape descriptor. In this paper we study the trade-off between stability and quality of these shape descriptors. We first show that there is no stateless algorithm, which depends only on the input points in one time step and not on previous states, that both approximates the minimum cost of a shape descriptor and achieves bounded speed. On the other hand, if we can use the previous state of the shape descriptor to compute the new state, then we can define "chasing" algorithms that attempt to follow the optimal orientation with bounded speed. Under mild conditions, we show that chasing algorithms with sufficient bounded speed approximate the optimal cost at every time step for oriented bounding boxes and strips, but not for principal components. The analysis of such chasing algorithms is challenging and has received little attention in literature, hence we believe that our methods used to perform this analysis are of independent interest.

  － BibTeX
  

  @article{stability-analysis-of-kinetic-orientation-based-shape-descriptors:2019,
      title = {Stability Analysis of Kinetic Orientation-Based Shape Descriptors},
      author = {Wouter Meulemans and Kevin Verbeek and Jules Wulms},
      year = {2019},
      bookTitle = {arXiv},
  }
  

  [ PDF ]
  
• Computing Stable Demers Cartograms
  Soeren Nickel, Max Sondag, Wouter Meulemans, Markus Chimani, Stephen Kobourov, Jaakko Peltonen, and Martin Nöllenburg.
  27th International Symposium Graph Drawing and Network Visualization (GD), pp. 46—60, 2019.
  
  － Abstract
  

  Cartograms are popular for visualizing numerical data for map regions. Maintaining correct adjacencies is a primary quality criterion for cartograms. When there are multiple data values per region (over time or different datasets) shown as animated or juxtaposed cartograms, preserving the viewer’s mental-map in terms of stability between cartograms is another important criterion. We present a method to compute stable Demers cartograms, where each region is shown as a square and similar data yield similar cartograms. We enforce orthogonal separation constraints with linear programming, and measure quality in terms of keeping adjacent regions close (cartogram quality) and using similar positions for a region between the different data values (stability). Our method guarantees ability to connect most lost adjacencies with minimal leaders. Experiments show our method yields good quality and stability.

  － BibTeX
  

  @article{computing-stable-demers-cartograms:2019,
      title = {Computing Stable Demers Cartograms},
      author = {Soeren Nickel and Max Sondag and Wouter Meulemans and Markus Chimani and Stephen Kobourov and Jaakko Peltonen and Martin Nöllenburg},
      year = {2019},
      bookTitle = {27th International Symposium Graph Drawing and Network Visualization (GD)},
  }
  

  [ PDF ]
  
• Convex Polygons in Cartesian Products
  Jean Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot.
  35th International Symposium on Computational Geometry, SoCG 2019, 2019.
  
  － Abstract
  

  <p>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 Ω(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 ∈ ℕ), and obtain a tight lower bound of Ω(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.</p>

  － BibTeX
  

  @article{convex-polygons-in-cartesian-products:2019,
      title = {Convex Polygons in Cartesian Products},
      author = {Jean Lou De Carufel and Adrian Dumitrescu and Wouter Meulemans and Tim Ophelders and Claire Pennarun and Csaba D. Tóth and Sander Verdonschot},
      year = {2019},
      bookTitle = {35th International Symposium on Computational Geometry, SoCG 2019},
  }
  

  [ PDF ]
  
• Maximum Physically Consistent Trajectories
  Bram Custers, Mees van de Kerkhof, Wouter Meulemans, Bettina Speckmann, and Frank Staals.
  SIGSPATIAL '19: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 79—88, 2019.
  
  － Abstract
  

  <p>Trajectories are usually collected with physical sensors, which are prone to errors and cause outliers in the data. We aim to identify such outliers via the physical properties of the tracked entity, that is, we consider its physical possibility to visit combinations of measurements. We describe optimal algorithms to compute maximum subsequences of measurements that are consistent with (simplified) physics models. Our results are output-sensitive with respect to the number k of outliers in a trajectory of n measurements. Specifically, we describe an O(n logn log ²k) time algorithm for 2D trajectories using a model with unbounded acceleration but bounded velocity, and an O(nk) time algorithm for any model where consistency is "concatenable": a consistent subsequence that ends where another begins together form a consistent sequence. We also consider acceleration-bounded models which are not concatenable. We show how to compute the maximum subsequence for such models in O(nk ²logk) time, under appropriate realism conditions. Finally, we experimentally explore the performance of our algorithms on several large real-world sets of trajectories. Our experiments show that we are generally able to retain larger fractions of noisy trajectories than previous work and simpler greedy approaches. We also observe that the speed-bounded model may in practice approximate the acceleration-bounded model quite well, though we observed some variation between datasets. </p>

  － BibTeX
  

  @article{maximum-physically-consistent-trajectories:2019,
      title = {Maximum Physically Consistent Trajectories},
      author = {Bram Custers and Mees van de Kerkhof and Wouter Meulemans and Bettina Speckmann and Frank Staals},
      year = {2019},
      bookTitle = {SIGSPATIAL '19: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems},
  }
  

• Topological Stability of Kinetic k-Centers
  Ivor van der Hoog, Marc van Kreveld, Wouter Meulemans, Kevin Verbeek, and Jules Wulms.
  WALCOM, pp. 43—55, 2019.
  
  － Abstract
  

  <p>We study the k-center problem in a kinetic setting: given a set of continuously moving points P in the plane, determine a set of k (moving) disks that cover P at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model is very hard to work with. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of k-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove upper and lower bounds on the ratio between the radii of an optimal but unstable solution and the radii of a topologically stable solution—the topological stability ratio—considering various metrics and various optimization criteria. For k = 2 we provide tight bounds, and for small we can obtain nontrivial lower and upper bounds. Finally, we provide an algorithm to compute the topological stability ratio in polynomial time for constant k.</p>

  － BibTeX
  

  @article{topological-stability-of-kinetic-k-centers:2019,
      title = {Topological Stability of Kinetic k-Centers},
      author = {Ivor van der Hoog and Marc van Kreveld and Wouter Meulemans and Kevin Verbeek and Jules Wulms},
      year = {2019},
      bookTitle = {WALCOM},
  }
  

  [ PDF ]
  
• Understanding Movement in Context with Heterogeneous Data
  Onur Derin, Aniket Mitra, Matei Stroila, Bram Custers, Wouter Meulemans, Marcel Roeloffzen, and Kevin Verbeek.
  MOVE++ 2019 - Proceedings of the 1st ACM SIGSPATIAL International Workshop on Computing with Multifaceted Movement Data, 2019.
  
  － Abstract
  

  <p>Movement data, as captured by myriad sensors, has been growing exponentially. Hence, multidisciplinary approaches for analyzing movement has become feasible. Though, movement pertains to a large variety of domains and applications, the focus of this position paper is understanding human movement (mobility) in various forms. We position maps as heterogeneous, multidimensional and digital representation of reality and advocate their role in contextualizing movement. We overview the main problems for analyzing human mobility with special attention to movement in context, leveraging heterogeneous data. We review the state-of-The-Art in solving these problems and describe remaining open problems and challenges for future work. Finally, we offer a view of existing as well as future mapping and location services that could enable these.</p>

  － BibTeX
  

  @article{understanding-movement-in-context-with-heterogeneous-data:2019,
      title = {Understanding Movement in Context with Heterogeneous Data},
      author = {Onur Derin and Aniket Mitra and Matei Stroila and Bram Custers and Wouter Meulemans and Marcel Roeloffzen and Kevin Verbeek},
      year = {2019},
      bookTitle = {MOVE++ 2019 - Proceedings of the 1st ACM SIGSPATIAL International Workshop on Computing with Multifaceted Movement Data},
  }
  

  [ PDF ]
  
• Concentric Set Schematization
  M.A. Bekos, Fabian Frank, Wouter Meulemans, Peter Rodgers, and André Schulz.
  2019.
  
  － Abstract
  

  Sets can be visualized in various ways and settings. An important<br/>distinction between techniques is based on whether the elements<br/>have a spatial location that is to be used for the visualization; for<br/>example, the elements are cities on a map. Strictly adhering to such<br/>location may severely limit the visualization and force overlay, intersections and other forms of clutter. On the other hand, completely<br/>ignoring the spatial dimension omits information and may hide spatial patterns in the data. In this abstract, we present ongoing research<br/>on a method that is in between spatial and nonspatial visualizations.<br/>The main idea is to schematize (move) the spatial locations onto<br/>concentric circles, to improve the visualization of the set system<br/>while roughly maintaining spatial structure.<br/>

  － BibTeX
  

  @article{concentric-set-schematization:2019,
      title = {Concentric Set Schematization},
      author = {M.A. Bekos and Fabian Frank and Wouter Meulemans and Peter Rodgers and André Schulz},
      year = {2019},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Maximum Physically Consistent Trajectories
  Bram Custers, Mees van de Kerkhof, Wouter Meulemans, Bettina Speckmann, and Frank Staals.
  2019.
  
  － Abstract
  

  We study the problem of detecting outlying measurements in a GPS trajectory. Our method considers the physical possibility for the tracked object to visit combinations of measurements,using simplified physics models. We aim to compute the maximum subsequence of the measurements that is consistent with a given physics model. We give an O(n log³ n) time algorithm for 2D-trajectories in a model with unbounded acceleration but bounded velocity, and an output-sensitive algorithm for any model where consistency checks can be done in O(1) time and consistency is transitive.

  － BibTeX
  

  @article{maximum-physically-consistent-trajectories:2019,
      title = {Maximum Physically Consistent Trajectories},
      author = {Bram Custers and Mees van de Kerkhof and Wouter Meulemans and Bettina Speckmann and Frank Staals},
      year = {2019},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Stability Analysis of Kinetic Oriented Bounding Boxes
  Wouter Meulemans, Kevin Verbeek, and Jules Wulms.
  pp. 39:1—39:7, 2019.
  
  － Abstract
  

  We study the oriented bounding box on a set of continuously moving points. <br/>The smallest oriented bounding box is the smallest bounding box, oriented to minimize the area. This optimal orientation may be very unstable as the points are moving, which is undesirable in many practical scenarios. Alternatively, we can bound the speed with which the orientation of the bounding box may change. However, this can increase the area of the resulting bounding box. In this paper we study the trade-off between stability and quality of the oriented bounding box. <br/><br/>We define a "chasing" algorithm that attempts to follow the optimal orientation with bounded speed. Under mild conditions, we show that chasing algorithms with sufficient speed approximate the optimal area at every time step for oriented bounding boxes. The analysis of such chasing algorithms is challenging and has received little attention in literature. Hence we believe that our methods used to perform this analysis are of independent interest.

  － BibTeX
  

  @article{stability-analysis-of-kinetic-oriented-bounding-boxes:2019,
      title = {Stability Analysis of Kinetic Oriented Bounding Boxes},
      author = {Wouter Meulemans and Kevin Verbeek and Jules Wulms},
      year = {2019},
      bookTitle = {},
  }
  

  [ PDF ]
  

2018

• Drawing Planar Graphs with Few Geometric Primitives
  Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans, and André Schulz.
  Journal of Graph Algorithms and Applications, 22(2):357—387, 2018.
  
  － Abstract
  

  We define the visual complexity of a plane graph drawing to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g., one needs only one line segment to draw a path with an arbitrary number of edges). Let n denote the number of vertices of a graph. We show that trees can be drawn with 3n/4<br/>straight-line segments on a polynomial grid, and with n/2 straight-line segments on a quasi-polynomial grid. Further, we present an algorithm for drawing planar 3-trees with (8n−17)/3 segments on an O(n)×O(n2) grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with 3n/2 edges on an O(n)×O(n2) grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only (5n−11)/3 arcs. This is significantly smaller than the lower bound of 2n for line segments for a nontrivial graph class.

  － BibTeX
  

  @article{drawing-planar-graphs-with-few-geometric-primitives:2018,
      title = {Drawing Planar Graphs with Few Geometric Primitives},
      author = {Gregor Hültenschmidt and Philipp Kindermann and Wouter Meulemans and André Schulz},
      year = {2018},
      bookTitle = {Journal of Graph Algorithms and Applications},
  }
  

  [ PDF ]
  
• A Framework for Algorithm Stability and Its Application to Kinetic Euclidean MSTs
  Wouter Meulemans, Bettina Speckmann, Kevin Verbeek, and Jules Wulms.
  LATIN 2018: Theoretical Informatics, pp. 805—819, 2018.
  
  － Abstract
  

  <p>We say that an algorithm is stable if small changes in the input result in small changes in the output. This kind of algorithm stability is particularly relevant when analyzing and visualizing time-varying data. Stability in general plays an important role in a wide variety of areas, such as numerical analysis, machine learning, and topology, but is poorly understood in the context of (combinatorial) algorithms. In this paper we present a framework for analyzing the stability of algorithms. We focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes. Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability. We demonstrate the use of our stability framework by applying it to kinetic Euclidean minimum spanning trees.</p>

  － BibTeX
  

  @article{a-framework-for-algorithm-stability-and-its-application-to-kinetic-euclidean-msts:2018,
      title = {A Framework for Algorithm Stability and Its Application to Kinetic Euclidean MSTs},
      author = {Wouter Meulemans and Bettina Speckmann and Kevin Verbeek and Jules Wulms},
      year = {2018},
      bookTitle = {LATIN 2018: Theoretical Informatics},
  }
  

  [ PDF ]
  
• Competitive Searching for a Line on a Line Arrangement
  Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans.
  29th International Symposium on Algorithms and Computation, ISAAC 2018, 2018.
  
  － Abstract
  

  <p>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 Ω(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.</p>

  － BibTeX
  

  @article{competitive-searching-for-a-line-on-a-line-arrangement:2018,
      title = {Competitive Searching for a Line on a Line Arrangement},
      author = {Quirijn Bouts and Thom Castermans and Arthur van Goethem and Marc van Kreveld and Wouter Meulemans},
      year = {2018},
      bookTitle = {29th International Symposium on Algorithms and Computation, ISAAC 2018},
  }
  

  [ PDF ]
  
• Experimental Analysis of the Accessibility of Drawings with Few Segments
  P. Kindermann, W. Meulemans, and A. Schulz.
  Graph Drawing and Network Visualization, pp. 52—64, 2018.
  
  － Abstract
  

  The visual complexity of a graph drawing is defined as the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges, e.g., one needs only one line segment to draw two collinear incident edges. We study the question if drawings with few segments have a better aesthetic appeal and help the user to asses the underlying graph. We design an experiment that investigates two different graph types (trees and sparse graphs), three different layout algorithms for trees, and two different layout algorithms for sparse graphs. We asked the users to give an aesthetic ranking on the layouts and to perform a furthest-pair or shortest-path task on the drawings.

  － BibTeX
  

  @article{experimental-analysis-of-the-accessibility-of-drawings-with-few-segments:2018,
      title = {Experimental Analysis of the Accessibility of Drawings with Few Segments},
      author = {P. Kindermann and W. Meulemans and A. Schulz},
      year = {2018},
      bookTitle = {Graph Drawing and Network Visualization},
  }
  

  [ PDF ]
  
• Geometry and Generation of a New Graph Planarity Game
  Rutger Kraaijer, Marc J. van Kreveld, Wouter Meulemans, and André van Renssen.
  Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018), 2018.
  
  － Abstract
  

  We introduce a new abstract graph game, SWAP PLANARITY, where the goal is to reach a state without edge intersections and a move consists of swapping the locations of two vertices connected by an edge. We analyze this puzzle game using concepts from graph theory and graph drawing, computational geometry, and complexity. Furthermore, we specify what good levels look like and we show how they can be generated. We also report on experiments that show how well the generation works.

  － BibTeX
  

  @article{geometry-and-generation-of-a-new-graph-planarity-game:2018,
      title = {Geometry and Generation of a New Graph Planarity Game},
      author = {Rutger Kraaijer and Marc J. van Kreveld and Wouter Meulemans and André van Renssen},
      year = {2018},
      bookTitle = {Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018)},
  }
  

• Optimal Algorithms for Compact Linear Layouts
  Willem Sonke, Kevin Verbeek, Wouter Meulemans, Eric Verbeek, and Bettina Speckmann.
  2018 IEEE Pacific Visualization Symposium, PacificVis 2018, pp. 1—10, 2018.
  
  － Abstract
  

  <p>Linear layouts are a simple and natural way to draw a graph: all vertices are placed on a single line and edges are drawn as arcs between the vertices. Despite its simplicity, a linear layout can be a very meaningful visualization if there is a particular order defined on the vertices. Common examples of such ordered - and often also directed - graphs are event sequences and processes. A main drawback of linear layouts are the usually (very) large aspect ratios of the resulting drawings, which prevent users from obtaining a good overview of the whole graph. In this paper we present a novel and versatile algorithm to optimally fold a linear layout of a graph such that it can be drawn nicely in a specified aspect ratio, while still clearly communicating the linearity of the layout. Our algorithm allows vertices to be drawn as blocks or rectangles of specified sizes to incorporate different drawing styles, label sizes, and even recursive structures. For reasonably-sized drawings the folded layout can be computed interactively. We demonstrate the applicability of our algorithm on graphs that represent process trees, a particular type of process model. Our algorithm arguably produces much more readable layouts than existing methods.</p>

  － BibTeX
  

  @article{optimal-algorithms-for-compact-linear-layouts:2018,
      title = {Optimal Algorithms for Compact Linear Layouts},
      author = {Willem Sonke and Kevin Verbeek and Wouter Meulemans and Eric Verbeek and Bettina Speckmann},
      year = {2018},
      bookTitle = {2018 IEEE Pacific Visualization Symposium, PacificVis 2018},
  }
  

• Short Plane Supports for Spatial Hypergraphs
  Thom Castermans, Mereke van Garderen, Wouter Meulemans, Martin Nöllenburg, and Xiaoru Yuan.
  Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings, pp. 53—66, 2018.
  
  － Abstract
  

  <p>A graph G = (V,E) is a support of a hypergraph H = (V,S) if every hyperedge induces a connected subgraph in G. Supports are used for certain types of hypergraph visualizations. In this paper we consider visualizing spatial hypergraphs, where each vertex has a fixed location in the plane. This is the case, e.g., when modeling set systems of geospatial locations as hypergraphs. By applying established aesthetic quality criteria we are interested in finding supports that yield plane straight-line drawings with minimum total edge length on the input point set V. We first show, from a theoretical point of view, that the problem is NP-hard already under rather mild conditions as well as a negative approximability results. Therefore, the main focus of the paper lies on practical heuristic algorithms as well as an exact, ILP-based approach for computing short plane supports. We report results from computational experiments that investigate the effect of requiring planarity and acyclicity on the resulting support length. Further, we evaluate the performance and trade-offs between solution quality and speed of several heuristics relative to each other and compared to optimal solutions.</p>

  － BibTeX
  

  @article{short-plane-supports-for-spatial-hypergraphs:2018,
      title = {Short Plane Supports for Spatial Hypergraphs},
      author = {Thom Castermans and Mereke van Garderen and Wouter Meulemans and Martin Nöllenburg and Xiaoru Yuan},
      year = {2018},
      bookTitle = {Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings},
  }
  

  [ PDF ]
  
• Social Network-Epistemology
  M. Alfano, S. Cunningham, W. Meulemans, I. Rutter, M. Sondag, B. Speckmann, and E. Sullivan.
  Proceedings - IEEE 14th International Conference on eScience, e-Science 2018, pp. 320—321, 2018.
  
  － BibTeX
  

  @article{social-network-epistemology:2018,
      title = {Social Network-Epistemology},
      author = {M. Alfano and S. Cunningham and W. Meulemans and I. Rutter and M. Sondag and B. Speckmann and E. Sullivan},
      year = {2018},
      bookTitle = {Proceedings - IEEE 14th International Conference on eScience, e-Science 2018},
  }
  

• The Painter’s Problem
  A.I. van Goethem, I. Kostitsyna, M.J. van Kreveld, W. Meulemans, M.F.M. Sondag, and J.J.H.M. Wulms.
  25th International Symposium on Graph Drawing and Network Visualization (GD), 10692 LNCS:492—505, 2018.
  
  － Abstract
  

  <p>Motivated by a new way of visualizing hypergraphs, we study the following problem. Consider a rectangular grid and a set of colors X Each cell s in the grid is assigned a subset of colors X_s ⊆ X and should be partitioned such that for each color c ∈ X_s at least one piece in the cell is identified with c. Cells assigned the empty color set remain white. We focus on the case where X = {red, blue}. Is it possible to partition each cell in the grid such that the unions of the resulting red and blue pieces form two connected polygons? We analyze the combinatorial properties and derive a necessary and sufficient condition for such a painting. We show that if a painting exists, there exists a painting with bounded complexity per cell. This painting has at most five colored pieces per cell if the grid contains white cells, and at most two colored pieces per cell if it does not.</p>

  － BibTeX
  

  @article{the-painter-s-problem:2018,
      title = {The Painter’s Problem},
      author = {A.I. van Goethem and I. Kostitsyna and M.J. van Kreveld and W. Meulemans and M.F.M. Sondag and J.J.H.M. Wulms},
      year = {2018},
      bookTitle = {25th International Symposium on Graph Drawing and Network Visualization (GD)},
  }
  

  [ PDF ]
  
• A Framework for Algorithm Stability and Its Application to Kinetic Euclidean MSTs
  W. Meulemans, B. Speckmann, K.A.B. Verbeek, and J.J.H.M. Wulms.
  pp. 11:1—11:6, 2018.
  
  － Abstract
  

  We say that an algorithm is stable if small changes in the input result in small changes in the output. This kind of algorithm stability is particularly relevant when analyzing and visualizing time-varying data. Stability in general plays an important role in a wide variety of areas, such as numerical analysis, machine learning, and topology, but is poorly understood in the context of (combinatorial) algorithms. <br/><br/>In this paper we present a framework for analyzing the stability of algorithms. We focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes. <br/>Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability. <br/>We demonstrate the use of topological stability by applying it to kinetic Euclidean minimum spanning trees.

  － BibTeX
  

  @article{a-framework-for-algorithm-stability-and-its-application-to-kinetic-euclidean-msts:2018,
      title = {A Framework for Algorithm Stability and Its Application to Kinetic Euclidean MSTs},
      author = {W. Meulemans and B. Speckmann and K.A.B. Verbeek and J.J.H.M. Wulms},
      year = {2018},
      bookTitle = {},
  }
  

  [ PDF ]
  
• On Convex Polygons in Cartesian Products
  Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Cs.D. Tóth, and Sander Verdonschot.
  pp. 39:1—39:6, 2018.
  
  － Abstract
  

  We study several problems concerning convex polygons whose vertices lie on a grid defined by the Cartesian product of two sets of n real numbers, using each coordinate at most once. First, we prove that all such grids contain a convex polygon with Ω(log n) vertices and that this bound is asymptotically tight. Second, we present two polynomial-time algorithms that find the largest<br/>convex polygon of a restricted type. These algorithms give an approximation of the unrestricted case. It is unknown whether the unrestricted problem can be solved in polynomial time.

  － BibTeX
  

  @article{on-convex-polygons-in-cartesian-products:2018,
      title = {On Convex Polygons in Cartesian Products},
      author = {Jean-Lou De Carufel and Adrian  Dumitrescu and Wouter Meulemans and Tim Ophelders and Claire Pennarun and Cs.D. Tóth and Sander Verdonschot},
      year = {2018},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Optimal Algorithms for Compact Linear Layouts
  Wouter Meulemans, Willem Sonke, Bettina Speckmann, Eric Verbeek, and Kevin Verbeek.
  pp. 10:1—10:6, 2018.
  
  － Abstract
  

  Linear layouts are a simple and natural way to draw a graph: all vertices are placed on a single line and edges are drawn as arcs between the vertices. Despite its simplicity, a linear layout can be a very meaningful visualization if there is a particular order defined on the vertices. Common examples of such ordered - and often also directed - graphs are event sequences and processes: public transport systems tracking passenger check-in and check-out, banks checking online transactions, or hospitals recording the paths of patients through their system, to name a few. A main drawback of linear layouts are the usually (very) large aspect ratios of the resulting drawings, which prevent users from obtaining a good overview of the whole graph. In this paper we present a novel and versatile algorithm to optimally fold a linear layout of a graph such that it can be drawn effectively in a specified aspect ratio, while still clearly communicating the linearity of the layout.

  － BibTeX
  

  @article{optimal-algorithms-for-compact-linear-layouts:2018,
      title = {Optimal Algorithms for Compact Linear Layouts},
      author = {Wouter Meulemans and Willem Sonke and Bettina Speckmann and Eric Verbeek and Kevin Verbeek},
      year = {2018},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Short Plane Support Trees for Hypergraphs
  Thom Castermans, Mereke van Garderen, Wouter Meulemans, Martin Nöllenburg, and Xiaoru Yuan.
  pp. 35:1—35:6, 2018.
  
  － Abstract
  

  In many domains, the aggregation or classification of data elements leads to various intersecting sets. To allow for intuitive exploration and analysis of such data, set visualization aims to represent the elements and sets graphically. In more theoretical literature, such set systems are often referred to as hypergraphs. A support graph is a notion for drawing such a hypergraph, understood as a regular graph spanning the same vertices (elements), in which each hyperedge (set) induces a connected subgraph.<br/><br/>In this paper, we investigate finding a support graph of a hypergraph with fixed vertex locations under various constraints. We focus on enforcing planarity using a straight-line embedding, while minimizing the total length of the edges of the support graph, and consider the effect of the additional requirement that the support graph is acyclic.

  － BibTeX
  

  @article{short-plane-support-trees-for-hypergraphs:2018,
      title = {Short Plane Support Trees for Hypergraphs},
      author = {Thom Castermans and Mereke van Garderen and Wouter Meulemans and Martin Nöllenburg and Xiaoru Yuan},
      year = {2018},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Topological Stability of Kinetic k-Centers
  Ivor van der Hoog, Marc J. van Kreveld, Wouter Meulemans, Kevin Verbeek, and Jules Wulms.
  pp. 2:1—2:3, 2018.
  
  － Abstract
  

  We study the k-center problem in a kinetic setting: given a set of continuously moving points P in the plane, determine a set of k (moving) disks that cover P at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model is very hard to work with. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of k-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove an upper and lower bound on the ratio between the maximum radius of an optimal but unstable solution and the maximum radius of a topologically stable solution---the topological stability ratio.

  － BibTeX
  

  @article{topological-stability-of-kinetic-k-centers:2018,
      title = {Topological Stability of Kinetic k-Centers},
      author = {Ivor van der Hoog and Marc J. van Kreveld and Wouter Meulemans and Kevin Verbeek and Jules Wulms},
      year = {2018},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Assessing Dot-Map Aggregations
  Wouter Meulemans and Martijn Tennekes.
  2018.
  
  － Abstract
  

  Compositional geospatial data can be visualized as dot maps, where the color of each dot represents its class. For interactive dots maps, where it is possible to zoom out in order to see the global picture, it is often needed to aggregate the dots. Hence, we face the following aggregation problem: let M be an input matrix where each cell is assigned a class; find an aggregated matrix A in which each cell aligns with k by k cells of M such that A is a good summary of M.<br/>We distinguish three dimensions of “good summary”: class  balance, representation and presence. The first is holistic, whereas the other<br/>two capture spatial aspects. We propose a simple heuristic algorithm

  － BibTeX
  

  @article{assessing-dot-map-aggregations:2018,
      title = {Assessing Dot-Map Aggregations},
      author = {Wouter Meulemans and Martijn Tennekes},
      year = {2018},
      bookTitle = {},
  }
  

  [ PDF ]
  
• On Minimal-Displacement Overlap Removal
  Wouter Meulemans.
  2018.
  
  － Abstract
  

  In the context of visualizing spatial data using proportional symbols, the following problem often arises: given a set of overlapping squares of varying sizes, reposition the squares as to remove the overlap while minimizing the displacement of the squares, constrained to maintain the orthogonal order. Though this problem is NP-hard, we show that rotating the squares by 45 degrees into diamonds allows for a linear or convex quadratic program and is thus efficiently solvable even for relatively large instances.

  － BibTeX
  

  @article{on-minimal-displacement-overlap-removal:2018,
      title = {On Minimal-Displacement Overlap Removal},
      author = {Wouter Meulemans},
      year = {2018},
      bookTitle = {},
  }
  

  [ PDF ]
  

2017

• A Framework for Algorithm Stability
  W. Meulemans, B. Speckmann, K.A.B. Verbeek, and J. Wulms.
  arXiv, 2017.
  
  － Abstract
  

  We say that an algorithm is stable if small changes in the input result in small changes in the output. Algorithm stability plays an important role when analyzing and visualizing time-varying data. However, so far, there are only few theoretical results on the stability of algorithms, possibly due to a lack of theoretical analysis tools. In this paper we present a framework for analyzing the stability of algorithms. We focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes. Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability. We demonstrate the use of our stability framework by applying it to kinetic Euclidean minimum spanning trees.

  － BibTeX
  

  @article{a-framework-for-algorithm-stability:2017,
      title = {A Framework for Algorithm Stability},
      author = {W. Meulemans and B. Speckmann and K.A.B. Verbeek and J. Wulms},
      year = {2017},
      bookTitle = {arXiv},
  }
  

  [ PDF ]
  
• Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms &amp; Experiments
  A. Igamberdiev, W. Meulemans, and A. Schulz.
  Journal of Graph Algorithms and Applications, 21(4):561—588, 2017.
  
  － Abstract
  

  A drawing of a graph can be understood as an arrangement of geometric objects. In the most natural setting the arrangement is formed by straight-line segments. Every cubic planar 3-connected graph with n<br/>n<br/> vertices has such a drawing with only n/2+3<br/>n/2+3<br/> segments, matching the lower bound. This result is due to Mondal et al. [J. of Comb. Opt., 25], who gave an algorithm for constructing such drawings. We introduce two new algorithms that also produce drawings with n/2+3<br/>n/2+3<br/> segments. One algorithm is based on a sequence of dual edge contractions, the other is based on a recursion of nested cycles. We also show a flaw in the algorithm of Mondal et al. and present a fix for it. We then compare the performance of these three algorithms by measuring angular resolution, edge length and face aspect ratio of the constructed drawings. We observe that the corrected algorithm of Mondal et al. mostly outperforms the other algorithms, especially in terms of angular resolution. However, the new algorithms perform better in terms of edge length and minimal face aspect ratio.

  － BibTeX
  

  @article{drawing-planar-cubic-3-connected-graphs-with-few-segments-algorithms-amp-experiments:2017,
      title = {Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms & Experiments},
      author = {A. Igamberdiev and W. Meulemans and A. Schulz},
      year = {2017},
      bookTitle = {Journal of Graph Algorithms and Applications},
  }
  

• Drawing Planar Graphs with Few Geometric Primitives
  G. Hültenschmidt, P. Kindermann, W. Meulemans, and A. Schulz.
  arXiv, 2017.
  
  － Abstract
  

  We define the emph{visual complexity of a plane graph drawing to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g., one needs only one line segment to draw two collinear edges of the same vertex). Let n denote the number of vertices of a graph. We show that trees can be drawn with 3n/4 straight-line segments on a polynomial grid, and with n/2 straight-line segments on a quasi-polynomial grid. Further, we present an algorithm for drawing planar 3-trees with (8n−17)/3 segments on an O(n)×O(n 2 ) grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with 3n/2 edges on an O(n)×O(n 2 ) grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only (5n−11)/3 arcs. This provides a significant improvement over the lower bound of 2n for line segments for a nontrivial graph class.

  － BibTeX
  

  @article{drawing-planar-graphs-with-few-geometric-primitives:2017,
      title = {Drawing Planar Graphs with Few Geometric Primitives},
      author = {G. Hültenschmidt and P. Kindermann and W. Meulemans and A. Schulz},
      year = {2017},
      bookTitle = {arXiv},
  }
  

  [ PDF ]
  
• Experimental Analysis of the Accessibility of Drawings with Few Segments
  P. Kindermann, W. Meulemans, and A. Schulz.
  arXiv, pp. 1—14, 2017.
  
  － Abstract
  

  The visual complexity of a graph drawing is defined as the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges, e.g., one needs only one line segment to draw two collinear incident edges. We study the question if drawings with few segments have a better aesthetic appeal and help the user to asses the underlying graph. We design an experiment that investigates two different graph types (trees and sparse graphs), three different layout algorithms for trees, and two different layout algorithms for sparse graphs. We asked the users to give an aesthetic ranking on the layouts and to perform a furthest-pair or shortest-path task on the drawings.

  － BibTeX
  

  @article{experimental-analysis-of-the-accessibility-of-drawings-with-few-segments:2017,
      title = {Experimental Analysis of the Accessibility of Drawings with Few Segments},
      author = {P. Kindermann and W. Meulemans and A. Schulz},
      year = {2017},
      bookTitle = {arXiv},
  }
  

  [ PDF ]
  
• Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance
  K.A. Buchin, M. Buchin, W. Meulemans, and W. Mulzer.
  Discrete and Computational Geometry, 58(1):180—216, 2017.
  
  － Abstract
  

  Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One popular measure is the Fréchet distance. Since it was proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original O(n 2 logn) O(n2log⁡n) algorithm by Alt and Godau for computing the Fréchet distance remains the state of the art (here, n denotes the number of edges on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard. In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Fréchet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Fréchet distance between two polygonal curves in time O(n 2 logn − − − − √ (loglogn) 3/2 ) O(n2log⁡n(log⁡log⁡n)3/2) on a pointer machine and in time O(n 2 (loglogn) 2 ) O(n2(log⁡log⁡n)2) on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth O(n 2−ε ) O(n2−ε) , for some ε&gt;0 ε&gt;0 . We believe that this reveals an intriguing new aspect of this well-studied problem. Finally, we show how to obtain the first subquadratic algorithm for computing the weak Fréchet distance on a word RAM.

  － BibTeX
  

  @article{four-soviets-walk-the-dog-improved-bounds-for-computing-the-fr-chet-distance:2017,
      title = {Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance},
      author = {K.A. Buchin and M. Buchin and W. Meulemans and W. Mulzer},
      year = {2017},
      bookTitle = {Discrete and Computational Geometry},
  }
  

  [ PDF ]
  
• Map LineUps: Effects of Spatial Structure on Graphical Inference
  Roger Beecham, Jason Dykes, Wouter Meulemans, Aidan Slingsby, Cagatay Turkay, and Jo Wood.
  IEEE Transactions on Visualization and Computer Graphics, 23(1):391—400, 2017.
  
  － Abstract
  

  Fundamental to the effective use of visualization as an analytic and descriptive tool is the assurance that presenting data visually provides the capability of making inferences from what we see. This paper explores two related approaches to quantifying the confidence we may have in making visual inferences from mapped geospatial data. We adapt Wickham et al.'s `Visual Line-up' method as a direct analogy with Null Hypothesis Significance Testing (NHST) and propose a new approach for generating more credible spatial null hypotheses. Rather than using as a spatial null hypothesis the unrealistic assumption of complete spatial randomness, we propose spatially autocorrelated simulations as alternative nulls. We conduct a set of crowdsourced experiments (n=361) to determine the just noticeable difference (JND) between pairs of choropleth maps of geographic units controlling for spatial autocorrelation (Moran's I statistic) and geometric configuration (variance in spatial unit area). Results indicate that people's abilities to perceive differences in spatial autocorrelation vary with baseline autocorrelation structure and the geometric configuration of geographic units. These results allow us, for the first time, to construct a visual equivalent of statistical power for geospatial data. Our JND results add to those provided in recent years by Klippel et al. (2011), Harrison et al. (2014) and Kay &amp; Heer (2015) for correlation visualization. Importantly, they provide an empirical basis for an improved construction of visual line-ups for maps and the development of theory to inform geospatial tests of graphical inference.

  － BibTeX
  

  @article{map-lineups-effects-of-spatial-structure-on-graphical-inference:2017,
      title = {Map LineUps: Effects of Spatial Structure on Graphical Inference},
      author = {Roger Beecham and Jason Dykes and Wouter Meulemans and Aidan Slingsby and Cagatay Turkay and Jo Wood},
      year = {2017},
      bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
  }
  

  [ PDF ]
  [ PDF ]
  
• Small Multiples with Gaps
  Wouter Meulemans, Jason Dykes, Aidan Slingsby, Cagatay Turkay, and Jo Wood.
  IEEE Transactions on Visualization and Computer Graphics, 23(1):381—390, 2017.
  
  － Abstract
  

  Small multiples enable comparison by providing different views of a single data set in a dense and aligned manner. A common frame defines each view, which varies based upon values of a conditioning variable. An increasingly popular use of this technique is to project two-dimensional locations into a gridded space (e.g. grid maps), using the underlying distribution both as the conditioning variable and to determine the grid layout. Using whitespace in this layout has the potential to carry information, especially in a geographic context. Yet, the effects of doing so on the spatial properties of the original units are not understood. We explore the design space offered by such small multiples with gaps. We do so by constructing a comprehensive suite of metrics that capture properties of the layout used to arrange the small multiples for comparison (e.g. compactness and alignment) and the preservation of the original data (e.g. distance, topology and shape). We study these metrics in geographic data sets with varying properties and numbers of gaps. We use simulated annealing to optimize for each metric and measure the effects on the others. To explore these effects systematically, we take a new approach, developing a system to visualize this design space using a set of interactive matrices. We find that adding small amounts of whitespace to small multiple arrays improves some of the characteristics of 2D layouts, such as shape, distance and direction. This comes at the cost of other metrics, such as the retention of topology. Effects vary according to the input maps, with degree of variation in size of input regions found to be a factor. Optima exist for particular metrics in many cases, but at different amounts of whitespace for different maps. We suggest multiple metrics be used in optimized layouts, finding topology to be a primary factor in existing manually-crafted solutions, followed by a trade-off between shape and displacement. But the rich range of possible optimized layouts leads us to challenge single-solution thinking; we suggest to consider alternative optimized layouts for small multiples with gaps. Key to our work is the systematic, quantified and visual approach to exploring design spaces when facing a trade-off between many competing criteria-an approach likely to be of value to the analysis of other design spaces.

  － BibTeX
  

  @article{small-multiples-with-gaps:2017,
      title = {Small Multiples with Gaps},
      author = {Wouter Meulemans and Jason Dykes and Aidan Slingsby and Cagatay Turkay and Jo Wood},
      year = {2017},
      bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
  }
  

  [ PDF ]
  [ PDF ]
  
• The Painter's Problem: Covering a Grid with Colored Connected Polygons
  A.I. van Goethem, I. Kostitsyna, M. van Kreveld, W. Meulemans, M.F.M. Sondag, and J.J.H.M. Wulms.
  arXiv, 2017.
  
  － Abstract
  

  Motivated by a new way of visualizing hypergraphs, we study the following problem. Consider a rectangular grid and a set of colors χ. Each cell s in the grid is assigned a subset of colors χs⊆χ and should be partitioned such that for each color c∈χs at least one piece in the cell is identified with c. Cells assigned the empty color set remain white. We focus on the case where χ={red,blue}. Is it possible to partition each cell in the grid such that the unions of the resulting red and blue pieces form two connected polygons? We analyze the combinatorial properties and derive a necessary and sufficient condition for such a painting. We show that if a painting exists, there exists a painting with bounded complexity per cell. This painting has at most five colored pieces per cell if the grid contains white cells, and at most two colored pieces per cell if it does not.

  － BibTeX
  

  @article{the-painter-s-problem-covering-a-grid-with-colored-connected-polygons:2017,
      title = {The Painter's Problem: Covering a Grid with Colored Connected Polygons},
      author = {A.I. van Goethem and I. Kostitsyna and M. van Kreveld and W. Meulemans and M.F.M. Sondag and J.J.H.M. Wulms},
      year = {2017},
      bookTitle = {arXiv},
  }
  

  [ PDF ]
  
• Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary
  B. Burton, E.W. Chambers, M.J. Van Kreveld, W. Meulemans, T.A.E. Ophelders, and B. Speckmann.
  Proc. 25th European Symposium on Algorithms (ESA), pp. 1—14, 2017.
  
  － Abstract
  

  <p>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.</p>

  － BibTeX
  

  @article{computing-optimal-homotopies-over-a-spiked-plane-with-polygonal-boundary:2017,
      title = {Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary},
      author = {B. Burton and E.W. Chambers and M.J. Van Kreveld and W. Meulemans and T.A.E. Ophelders and B. Speckmann},
      year = {2017},
      bookTitle = {Proc. 25th European Symposium on Algorithms (ESA)},
  }
  

  [ PDF ]
  
• Discretized Approaches to Schematization
  M. Löffler and W. Meulemans.
  29th Canadian Conference on Computational Geometry (CCCG), pp. 220—225, 2017.
  
  － Abstract
  

  For both the Fréchet distance and the symmetric difference, we show that finding the simple polygon S restricted to a grid that best resembles a simple polygon P is NP-complete, even if: (1) we require that S and P have equal area; (2) we require turns to occur in a specified sequence for the Fréchet distance; (3) we permit S to have holes for the symmetric difference. Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved.

  － BibTeX
  

  @article{discretized-approaches-to-schematization:2017,
      title = {Discretized Approaches to Schematization},
      author = {M. Löffler and W. Meulemans},
      year = {2017},
      bookTitle = {29th Canadian Conference on Computational Geometry (CCCG)},
  }
  

  [ PDF ]
  
• Drawing Planar Graphs with Few Geometric Primitives
  G. Hültenschmidt, P. Kindermann, W. Meulemans, and A. Schulz.
  43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 316—329, 2017.
  
  － Abstract
  

  We define the visual complexity of a plane graph drawing to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g., one needs only one line segment to draw two collinear edges of the same vertex). Let n denote the number of vertices of a graph. We show that trees can be drawn with 3n / 4 straight-line segments on a polynomial grid, and with n / 2 straight-line segments on a quasi-polynomial grid. Further, we present an algorithm for drawing planar 3-trees with (8n−17)/3 <br/>(8n−17)/3<br/> segments on an O(n)×O(n 2 ) <br/>O(n)×O(n2)<br/> grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with 3n / 2 edges on an O(n)×O(n 2 ) <br/>O(n)×O(n2)<br/> grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only (5n−11)/3 <br/>(5n−11)/3<br/> arcs. This provides a significant improvement over the lower bound of 2n for line segments for a nontrivial graph class.<br/>

  － BibTeX
  

  @article{drawing-planar-graphs-with-few-geometric-primitives:2017,
      title = {Drawing Planar Graphs with Few Geometric Primitives},
      author = {G. Hültenschmidt and P. Kindermann and W. Meulemans and A. Schulz},
      year = {2017},
      bookTitle = {43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)},
  }
  

• Efficient Trajectory Queries Under the Fréchet Distance (GIS Cup)
  K.A. Buchin, Y. Diez, T.W.T. van Diggelen, and W. Meulemans.
  Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), 2017.
  
  － Abstract
  

  Consider a set P of trajectories (polygonal lines in R2), and a query given by a trajectory Q and a threshold &amp;epsis; &gt; 0. To answer the query we wish to find all trajectories P ∈ P such that δF(P, Q) ≤ &amp;epsis;, where δF denotes the Fréchet distance. We present an approach to efficiently answer a large number of queries for the same set P. Key ingredients are (a) precomputing a spatial hash that allows us to quickly find trajectories that have endpoints near Q; (b) precomputing simplifications on all trajectories in P; (c) using the simplifications and optimizations of the decision algorithm to efficiently decide δF(P, Q) ≤ &amp;epsis; for most P ∈ P.

  － BibTeX
  

  @article{efficient-trajectory-queries-under-the-fr-chet-distance-gis-cup-:2017,
      title = {Efficient Trajectory Queries Under the Fréchet Distance (GIS Cup)},
      author = {K.A. Buchin and Y. Diez and T.W.T. van Diggelen and W. Meulemans},
      year = {2017},
      bookTitle = {Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)},
  }
  

  [ PDF ]
  
• Folding Free-Space Diagrams: Computing the Fréchet Distance Between 1-Dimensional Curves
  K.A. Buchin, J. Chun, A. Markovic, W. Meulemans, M. Löffler, Y. Okamoto, and T. Shiitada.
  33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia, pp. 641—645, 2017.
  
  － Abstract
  

  <p>By folding the free-space diagram for efficient preprocessing, we show that the Fréchet distance between 1D curves can be computed in O(nk log n) time, assuming one curve has ply k.</p>

  － BibTeX
  

  @article{folding-free-space-diagrams-computing-the-fr-chet-distance-between-1-dimensional-curves:2017,
      title = {Folding Free-Space Diagrams: Computing the Fréchet Distance Between 1-Dimensional Curves},
      author = {K.A. Buchin and J. Chun and A. Markovic and W. Meulemans and M. Löffler and Y. Okamoto and T. Shiitada},
      year = {2017},
      bookTitle = {33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia},
  }
  

  [ PDF ]
  

2016

• Area-Preserving Simplification and Schematization of Polygonal Subdivisions
  Kevin Buchin, Wouter Meulemans, André Van Renssen, and Bettina Speckmann.
  ACM Transactions on Spatial Algorithms and Systems , 2(1):1—36, 2016.
  
  － Abstract
  

  <p>In this article, we study automated simplification and schematization of territorial outlines. We present a quadratic-time simplification algorithm based on an operation called edge-move. We prove that the number of edges of any nonconvex simple polygon can be reduced with this operation. Moreover, edge-moves preserve area and topology and do not introduce new orientations. The latter property in particular makes the algorithm highly suitable for schematization in which all resulting lines are required to be parallel to one of a given set of lines (orientations). To obtain such a result, we need only to preprocess the input to use only lines that are parallel to one of the given set. We present an algorithm to enforce such orientation restrictions, again without changing area or topology. Experiments show that our algorithms obtain results of high visual quality.</p>

  － BibTeX
  

  @article{area-preserving-simplification-and-schematization-of-polygonal-subdivisions:2016,
      title = {Area-Preserving Simplification and Schematization of Polygonal Subdivisions},
      author = {Kevin Buchin and Wouter Meulemans and André Van Renssen and Bettina Speckmann},
      year = {2016},
      bookTitle = {ACM Transactions on Spatial Algorithms and Systems },
  }
  

  [ PDF ]
  [ PDF ]
  
• Computing the Fréchet Distance with a Retractable Leash
  K.A. Buchin, M.E. Buchin, R. van Leusden, W. Meulemans, and W. Mulzer.
  Discrete and Computational Geometry, 56(2):315—336, 2016.
  
  － Abstract
  

  All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fréchet distance between polygonal curves in Rd under polyhedral distance functions (e.g., L1 and L∞). We also get a (1+ε)-approximation of the Fréchet distance under the Euclidean metric, in quadratic time for any fixed ε&gt;0. For the exact Euclidean case, our framework currently yields an algorithm with running time O(n2log2n). However, we conjecture that it may eventually lead to a faster exact algorithm.

  － BibTeX
  

  @article{computing-the-fr-chet-distance-with-a-retractable-leash:2016,
      title = {Computing the Fréchet Distance with a Retractable Leash},
      author = {K.A. Buchin and M.E. Buchin and R. van Leusden and W. Meulemans and W. Mulzer},
      year = {2016},
      bookTitle = {Discrete and Computational Geometry},
  }
  

  [ PDF ]
  
• Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance
  Q.W. Bouts, I. Kostitsyna, M.J. van Kreveld, W. Meulemans, W. Sonke, and K.A.B. Verbeek.
  arXiv, 2016.
  
  － Abstract
  

  We show how to represent a simple polygon <i>P</i> by a grid (pixel-based) polygon <i>Q</i> that is simple and whose Hausdorff or Fréchet distance to <i>P</i> is small. For any simple polygon <i>P</i>, 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.

  － BibTeX
  

  @article{mapping-polygons-to-the-grid-with-small-hausdorff-and-fr-chet-distance:2016,
      title = {Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance},
      author = {Q.W. Bouts and I. Kostitsyna and M.J. van Kreveld and W. Meulemans and W. Sonke and K.A.B. Verbeek},
      year = {2016},
      bookTitle = {arXiv},
  }
  

  [ PDF ]
  
• Drawing Trees and Triangulations with Few Geometric Primitives
  G. Hültenschmidt, P. Kindermann, W. Meulemans, and A. Schulz.
  Abstracts of the 32nd European Workshop on Computational Geometry (EuroCG), 2016.
  
  － Abstract
  

  We define the visual complexity of a plane graph drawing to be the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g. you need only one line segment to draw two collinear edges of the same vertex). We show that trees can be drawn with 3n/4 straight-line segments on a polynomial grid, and with n/2 straight-line segments on a quasi-polynomial grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only (5n− 11)/3 arcs. This provides a significant improvement over the lower bound of 2n for line segments for a nontrivial graph class

  － BibTeX
  

  @article{drawing-trees-and-triangulations-with-few-geometric-primitives:2016,
      title = {Drawing Trees and Triangulations with Few Geometric Primitives},
      author = {G. Hültenschmidt and P. Kindermann and W. Meulemans and A. Schulz},
      year = {2016},
      bookTitle = {Abstracts of the 32nd European Workshop on Computational Geometry (EuroCG)},
  }
  

  [ PDF ]
  
• Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance
  Q.W. Bouts, Irina Kostitsyna, M.J. van Kreveld, W. Meulemans, W.M. Sonke, and K.A.B. Verbeek.
  Proc. 24th Annual European Symposium on Algorithms (ESA), pp. 1—16, 2016.
  
  － Abstract
  

  <p>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.</p>

  － BibTeX
  

  @article{mapping-polygons-to-the-grid-with-small-hausdorff-and-fr-chet-distance:2016,
      title = {Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance},
      author = {Q.W. Bouts and Irina Kostitsyna and M.J. van Kreveld and W. Meulemans and W.M. Sonke and K.A.B. Verbeek},
      year = {2016},
      bookTitle = {Proc. 24th Annual European Symposium on Algorithms (ESA)},
  }
  

  [ PDF ]
  
• Partitioning Polygons Via Graph Augmentation
  Jan-Henrik Haunert and Wouter Meulemans.
  Geographic Information Science, pp. 18—33, 2016.
  
  － Abstract
  

  We study graph augmentation under the dilation criterion. In our case, we consider a plane geometric graph G=(V,E) <br/>G=(V,E)<br/> and a set C of edges. We aim to add to G a minimal number of nonintersecting edges from C to bound the ratio between the graph-based distance and the Euclidean distance for all pairs of vertices described by C. Motivated by the problem of decomposing a polygon into natural subregions, we present an optimal linear-time algorithm for the case that P is a simple polygon and C models an internal triangulation of P. The algorithm admits some straightforward extensions. Most importantly, in pseudopolynomial time, it can approximate a solution of minimum total length or, if C is weighted, compute a solution of minimum total weight. We show that minimizing the total length or the total weight is weakly NP-hard.<br/><br/>Finally, we show how our algorithm can be used for two well-known problems in GIS: generating variable-scale maps and area aggregation.<br/>

  － BibTeX
  

  @article{partitioning-polygons-via-graph-augmentation:2016,
      title = {Partitioning Polygons Via Graph Augmentation},
      author = {Jan-Henrik Haunert and Wouter Meulemans},
      year = {2016},
      bookTitle = {Geographic Information Science},
  }
  

  [ PDF ]
  
• Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance
  Q.W. Bouts, I. Kostitsyna, M.J. van Kreveld, W. Meulemans, W.M. Sonke, and K.A.B. Verbeek.
  pp. 247—250, 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.

  － BibTeX
  

  @article{mapping-polygons-to-the-grid-with-small-hausdorff-and-fr-chet-distance:2016,
      title = {Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance},
      author = {Q.W. Bouts and I. Kostitsyna and M.J. van Kreveld and W. Meulemans and W.M. Sonke and K.A.B. Verbeek},
      year = {2016},
      bookTitle = {},
  }
  

  [ PDF ]
  

2015

• Exploring Curved Schematization of Territorial Outlines
  A.I. Goethem, van, W. Meulemans, B. Speckmann, and J.D. Wood.
  IEEE Transactions on Visualization and Computer Graphics, 21(8):889—902, 2015.
  
  － Abstract
  

  Hand-drawn schematized maps traditionally make extensive use of curves. However, there are few automated approaches for curved schematization; most previous work focuses on straight lines. We present a new algorithm for areapreserving curved schematization of territorial outlines. Our algorithm converts a simple polygon into a schematic crossing-free representation using circular arcs.We use two basic operations to iteratively replace consecutive arcs until the desired complexity is reached. Our results are not restricted to arcs ending at input vertices. The method can be steered towards different degrees of "curviness": we can encourage or discourage the use of arcs with a large central angle via a single parameter. Our method creates visually pleasing results even for very low output complexities. To evaluate the effectiveness of our design choices, we present a geometric evaluation of the resulting schematizations. Besides the geometric qualities of our algorithm, we also investigate the potential of curved schematization as a concept. We conducted an online user study investigating the effectiveness of curved schematizations compared to straight-line schematizations. While the visual complexity of curved shapes was judged higher than that of straight-line shapes, users generally preferred curved schematizations. We observed that curves significantly improved the ability of users to match schematized shapes of moderate complexity to their unschematized equivalents. Keywords: Schematization; algorithm; circular arcs; user study

  － BibTeX
  

  @article{exploring-curved-schematization-of-territorial-outlines:2015,
      title = {Exploring Curved Schematization of Territorial Outlines},
      author = {A.I. Goethem, van and W. Meulemans and B. Speckmann and J.D. Wood},
      year = {2015},
      bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
  }
  

  [ PDF ]
  [ PDF ]
  
• A Tale of Two Communities: Assessing Homophily in Node-Link Diagrams
  W. Meulemans and A. Schulz.
  Graph Drawing and Network Visualization, pp. 489—501, 2015.
  
  － Abstract
  

  Homophily is a concept in social network analysis that states that in a network a link is more probable, if the two individuals have a common characteristic. We study the question if an observer can assess homophily by looking at the node-link diagram of the network. We design an experiment that investigates three different layout algorithms and asks the users to estimate the degree of homophily in the displayed network. One of the layout algorithms is a classical force-directed method, the other two are designed to improve node distinction based on the common characteristic. We study how each of the three layout algorithms helps to get a fair estimate, and whether there is a tendency to over or underestimate the degree of homophily. The stimuli in our experiments use different network sizes and different proportions of the cluster sizes.

  － BibTeX
  

  @article{a-tale-of-two-communities-assessing-homophily-in-node-link-diagrams:2015,
      title = {A Tale of Two Communities: Assessing Homophily in Node-Link Diagrams},
      author = {W. Meulemans and A. Schulz},
      year = {2015},
      bookTitle = {Graph Drawing and Network Visualization},
  }
  

  [ PDF ]
  
• Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms &amp; Experiments
  A. Igamberdiev, W. Meulemans, and A. Schulz.
  Graph Drawing and Network Visualization, pp. 113—124, 2015.
  
  － BibTeX
  

  @article{drawing-planar-cubic-3-connected-graphs-with-few-segments-algorithms-amp-experiments:2015,
      title = {Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms & Experiments},
      author = {A. Igamberdiev and W. Meulemans and A. Schulz},
      year = {2015},
      bookTitle = {Graph Drawing and Network Visualization},
  }
  

  [ PDF ]
  
• Drawing Planar Cubic 3-Connected Graphs with Minimal Visual Complexity
  A. Igamberdiev, W. Meulemans, and A. Schulz.
  Abstracts of the 4th Young Researchers Forum (YRF), pp. 24—25, 2015.
  
  － BibTeX
  

  @article{drawing-planar-cubic-3-connected-graphs-with-minimal-visual-complexity:2015,
      title = {Drawing Planar Cubic 3-Connected Graphs with Minimal Visual Complexity},
      author = {A. Igamberdiev and W. Meulemans and A. Schulz},
      year = {2015},
      bookTitle = {Abstracts of the 4th Young Researchers Forum (YRF)},
  }
  

2014

• Automatische Schematisering Met Gebogen Lijnen
  A.I. Goethem, van, H.J. Haverkort, W. Meulemans, A. Reimer, B. Speckmann, and J.D. Wood.
  Geo-Info, 2014(2):10—13, 2014.
  
  － BibTeX
  

  @article{automatische-schematisering-met-gebogen-lijnen:2014,
      title = {Automatische Schematisering Met Gebogen Lijnen},
      author = {A.I. Goethem, van and H.J. Haverkort and W. Meulemans and A. Reimer and B. Speckmann and J.D. Wood},
      year = {2014},
      bookTitle = {Geo-Info},
  }
  

  [ PDF ]
  
• Exploring Curved Schematization
  A.I. van Goethem, W. Meulemans, B. Speckmann, and J.D. Wood.
  7th IEEE Pacific Visualization Symposium (PacificVis), pp. 1—8, 2014.
  
  － Abstract
  

  Hand-drawn schematized maps traditionally make extensive use of curves. However, there are few automated approaches for curved schematization most previous work focuses on straight lines. We present a new algorithm for area-preserving curved schematization of geographic outlines. Our algorithm converts a simple polygon into a schematic crossing-free representation using circular arcs. We use two basic operations to iteratively replace consecutive arcs until the desired complexity is reached. Our results are not restricted to arcs ending at input vertices. The method can be steered towards different degrees of 'curviness': we can encourage or discourage the use of arcs with a large central angle via a single parameter. Our method creates visually pleasing results even for very low output complexities. We conducted an online user study investigating the effectiveness of the curved schematizations compared to straight-line schematizations of equivalent complexity. While the visual complexity of the curved shapes was judged higher than those using straight lines, users generally preferred curved schematizations. We observed that curves significantly improved the ability of users to match schematized shapes of moderate complexity to their unschematized equivalents.

  － BibTeX
  

  @article{exploring-curved-schematization:2014,
      title = {Exploring Curved Schematization},
      author = {A.I. van Goethem and W. Meulemans and B. Speckmann and J.D. Wood},
      year = {2014},
      bookTitle = {7th IEEE Pacific Visualization Symposium (PacificVis)},
  }
  

  [ PDF ]
  
• Four Soviets Walk the Dog, with an Application to Alt's Conjecture
  K. Buchin, M. Buchin, W. Meulemans, and W. Mulzer.
  25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1399—1413, 2014.
  
  － Abstract
  

  Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One measure that is extremely popular is the Fréchet distance. Since it has been proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original O(n^2 log n) algorithm by Alt and Godau for computing the Fréchet distance remains the state of the art (here n denotes the number of vertices on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard.In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Fréchet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Fréchet distance between two polygonal curves in time O(n^2 \sqrt log n (log log n)^{3/2}) on a pointer machine and in time O(n^2 (log log n)^2) on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth O(n^{2¿}), for some ¿ &gt; 0. This provides evidence that the decision problem may not be 3SUM-hard after all and reveals an intriguing new aspect of this well-studied problem.

  － BibTeX
  

  @article{four-soviets-walk-the-dog-with-an-application-to-alt-s-conjecture:2014,
      title = {Four Soviets Walk the Dog, with an Application to Alt's Conjecture},
      author = {K. Buchin and M. Buchin and W. Meulemans and W. Mulzer},
      year = {2014},
      bookTitle = {25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  }
  

  [ PDF ]
  
• Map Schematization with Circular Arcs
  T. van Dijk, A.I. van Goethem, J.H. Haunert, W. Meulemans, and B. Speckmann.
  8th International Conference on Geographic Information Science (GIScience), pp. 1—17, 2014.
  
  － Abstract
  

  We present an algorithm to compute schematic maps with circular arcs. Our algorithm iteratively replaces two consecutive arcs with a single arc to reduce the complexity of the output map and thus to increase its level of abstraction. Our main contribution is a method for replacing arcs that meet at high-degree vertices. This allows us to greatly reduce the output complexity, even for dense networks. We experimentally evaluate the effectiveness of our algorithm in three scenarios: territorial outlines, road networks, and metro maps. For the latter, we combine our approach with an algorithm to more evenly distribute stations. Our experiments show that our algorithm produces high-quality results for territorial outlines and metro maps. However, the lack of caricature (exaggeration of typical features) makes it less useful for road networks.

  － BibTeX
  

  @article{map-schematization-with-circular-arcs:2014,
      title = {Map Schematization with Circular Arcs},
      author = {T. van Dijk and A.I. van Goethem and J.H. Haunert and W. Meulemans and B. Speckmann},
      year = {2014},
      bookTitle = {8th International Conference on Geographic Information Science (GIScience)},
  }
  

  [ PDF ]
  
• Similarity Measures and Algorithms for Cartographic Schematization
  W. Meulemans.
  2014.
  
  － BibTeX
  

  @article{similarity-measures-and-algorithms-for-cartographic-schematization:2014,
      title = {Similarity Measures and Algorithms for Cartographic Schematization},
      author = {W. Meulemans},
      year = {2014},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Faces of Science: Wouter Meulemans
  W. Meulemans.
  2014.
  
  － Abstract
  

  Published on Jun 3, 2014 Herkenbaar: reken maar! Als je naar de NS treinenkaart kijkt, dan zie je gelijk dat het om Nederland gaat. Terwijl je eigenlijk alleen maar een paar horizontale, verticale en diagonale lijnen ziet. Het is een schematische weergave van Nederland, die in één oogopslag als zodanig te herkennen is. Wouter Meulemans probeert computers te leren zelf zoiets te maken op basis van landkaarten. Geproduceerd door Fast Facts In opdracht van de KNAW en De Jonge Akademie Gefinancierd door de wetenschappelijke auteurs van Elsevier Science, ondersteund door Lira Auteursfonds Reprorecht Met dank aan: Kevin Buchin, Arthur van Goethem, Maximilian Konzack, Ali D. Mehrabi, Marcel Roeloffzen en Bettina Speckmann Met beelden van: Wouter Meulemans Gemaakt door: Jasmijn Snoijink 2014 In samenwerking met Camera &amp; montage: Jonathan Massey | Persistent Vision Muziek: Daan van West Grafisch ontwerp: SproetS Meer Faces of Science op facesofscience.nl

  － BibTeX
  

  @article{faces-of-science-wouter-meulemans:2014,
      title = {Faces of Science: Wouter Meulemans},
      author = {W. Meulemans},
      year = {2014},
      bookTitle = {},
  }
  

2013

• KelpFusion: a Hybrid Set Visualization Technique
  W. Meulemans, N. Henry Riche, B. Speckmann, B. Alper, and T. Dwyer.
  IEEE Transactions on Visualization and Computer Graphics, 19(11):1846—1858, 2013.
  
  － Abstract
  

  We present KelpFusion: a method for depicting set membership of items on a map or other visualization using continuous boundaries. KelpFusion is a hybrid representation that bridges hull techniques such as Bubble Sets and Euler Diagrams and line- and graph-based techniques such as LineSets and Kelp Diagrams. We describe an algorithm based on shortest-path graphs to compute KelpFusion visualizations. Based on a single parameter, the shortest-path graph varies from the minimal spanning tree to the convex hull of a point set. Shortest-path graphs aim to capture the shape of a point set and smoothly adapt to sets of varying densities. KelpFusion fills enclosed faces based on a set of simple legibility rules. We present the results of a controlled experiment comparing KelpFusion to Bubble Sets and LineSets. We conclude that KelpFusion outperforms Bubble Sets both in accuracy and completion time, and outperforms LineSets in completion time. Keywords: Information visualization, visualization techniques and methodologies

  － BibTeX
  

  @article{kelpfusion-a-hybrid-set-visualization-technique:2013,
      title = {KelpFusion: a Hybrid Set Visualization Technique},
      author = {W. Meulemans and N. Henry Riche and B. Speckmann and B. Alper and T. Dwyer},
      year = {2013},
      bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
  }
  

  [ PDF ]
  
• Topologically Safe Curved Schematisation
  A.I. Goethem, van, W. Meulemans, A. Reimer, H.J. Haverkort, and B. Speckmann.
  The Cartographic Journal, 50(3):276—285, 2013.
  
  － Abstract
  

  Traditionally schematised maps make extensive use of curves. However, automated methods for schematisation are mostly restricted to straight lines. We present a generic framework for topology-preserving curved schematisation that allows a choice of quality measures and curve types. The framework fits a curve to every part of the input. It uses Voronoi diagrams to ensure that curves fitted to disjoint parts do not intersect. The framework then employs a dynamic program to find an optimal schematisation using the fitted curves. Our fully-automated approach does not need critical points or salient features. We illustrate our framework with Bézier curves and circular arcs.

  － BibTeX
  

  @article{topologically-safe-curved-schematisation:2013,
      title = {Topologically Safe Curved Schematisation},
      author = {A.I. Goethem, van and W. Meulemans and A. Reimer and H.J. Haverkort and B. Speckmann},
      year = {2013},
      bookTitle = {The Cartographic Journal},
  }
  

  [ PDF ]
  
• Accentuating Focus Maps Via Partial Schematization
  T. van Dijk, A.I. van Goethem, J.H. Haunert, W. Meulemans, and B. Speckmann.
  21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), pp. 418—421, 2013.
  
  － Abstract
  

  We present an algorithm for schematized focus maps. Focus maps integrate a high detailed, enlarged focus region continuously in a given base map. Recent methods integrate both with such low distortion that the focus region becomes hard to identify. We combine focus maps with partial schematization to display distortion of the context and to emphasize the focus region. Schematization visually conveys geographical accuracy, while not increasing map complexity. We extend the focus-map algorithm to incorporate geometric proximity relationships and show how to combine focus maps with schematization in order to cater to different use cases.

  － BibTeX
  

  @article{accentuating-focus-maps-via-partial-schematization:2013,
      title = {Accentuating Focus Maps Via Partial Schematization},
      author = {T. van Dijk and A.I. van Goethem and J.H. Haunert and W. Meulemans and B. Speckmann},
      year = {2013},
      bookTitle = {21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)},
  }
  

  [ PDF ]
  
• Computing the Fréchet Distance with a Retractable Leash
  K. Buchin, M. Buchin, R. Leusden, van, W. Meulemans, and W. Mulzer.
  21st Annual European Symposium on Algorithms (ESA), pp. 241—252, 2013.
  
  － Abstract
  

  All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; then they use this oracle to find the optimum among a finite set of critical values. We present a novel approach that avoids the detour through the decision version. We demonstrate its strength by presenting a quadratic time algorithm for the Fréchet distance between polygonal curves in R^d under polyhedral distance functions, including L_1 and L_infinity. We also get a (1+eps)-approximation of the Fréchet distance under the Euclidean metric. For the exact Euclidean case, our framework currently gives an algorithm with running time O(n^2 log^2 n). However, we conjecture that it may eventually lead to a faster exact algorithm.

  － BibTeX
  

  @article{computing-the-fr-chet-distance-with-a-retractable-leash:2013,
      title = {Computing the Fréchet Distance with a Retractable Leash},
      author = {K. Buchin and M. Buchin and R. Leusden, van and W. Meulemans and W. Mulzer},
      year = {2013},
      bookTitle = {21st Annual European Symposium on Algorithms (ESA)},
  }
  

  [ PDF ]
  
• Topologically Safe Curved Schematization
  A.I. van Goethem, H.J. Haverkort, W. Meulemans, A. Reimer, and B. Speckmann.
  pp. 87—90, 2013.
  
  － Abstract
  

  Traditionally schematized maps make extensive use of curves. However, automated methods for schematization are mostly restricted to straight lines. We present a generic framework for topology-preserving curved schematization that allows a choice of quality measures and curve types. Our fully-automated approach does not need critical points or salient features. We illustrate our framework with Bézier curves and circular arcs.

  － BibTeX
  

  @article{topologically-safe-curved-schematization:2013,
      title = {Topologically Safe Curved Schematization},
      author = {A.I. van Goethem and H.J. Haverkort and W. Meulemans and A. Reimer and B. Speckmann},
      year = {2013},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Computing the Fréchet Distance with a Retractable Leash
  K. Buchin, M. Buchin, R. Leusden, van, W. Meulemans, and W. Mulzer.
  2013.
  
  － Abstract
  

  All known algorithms for the Fr\'echet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; then they use this oracle to find the optimum among a finite set of critical values. We present a novel approach that avoids the detour through the decision version. We demonstrate its strength by presenting a quadratic time algorithm for the Fr\'echet distance between polygonal curves in R^d under polyhedral distance functions, including L_1 and L_infty. We also get a (1+epsilon)-approximation of the Fr\'echet distance under the Euclidean metric. For the exact Euclidean case, our framework currently gives an algorithm with running time O(n^2 log^2 n). However, we conjecture that it may eventually lead to a faster exact algorithm.

  － BibTeX
  

  @article{computing-the-fr-chet-distance-with-a-retractable-leash:2013,
      title = {Computing the Fréchet Distance with a Retractable Leash},
      author = {K. Buchin and M. Buchin and R. Leusden, van and W. Meulemans and W. Mulzer},
      year = {2013},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Map Matching with Simplicity Constraints
  W. Meulemans.
  2013.
  
  － Abstract
  

  We study a map matching problem, the task of finding in an embedded graph a path that has low distance to a given curve in R^2. The Fr\'echet distance is a common measure for this problem. Efficient methods exist to compute the best path according to this measure. However, these methods cannot guarantee that the result is simple (i.e. it does not intersect itself) even if the given curve is simple. In this paper, we prove that it is in fact NP-complete to determine the existence a simple cycle in a planar straight-line embedding of a graph that has at most a given Fr\'echet distance to a given simple closed curve. We also consider the implications of our proof on some variants of the problem.

  － BibTeX
  

  @article{map-matching-with-simplicity-constraints:2013,
      title = {Map Matching with Simplicity Constraints},
      author = {W. Meulemans},
      year = {2013},
      bookTitle = {},
  }
  

  [ PDF ]
  

2012

• Locally Correct Fréchet Matchings
  K. Buchin, M. Buchin, W. Meulemans, and B. Speckmann.
  20th European Symposium on Algorithms (ESA), pp. 229—240, 2012.
  
  － Abstract
  

  The Fréchet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to "natural" matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such matching exists for two polygonal curves and give an O(N^3 log N) algorithm to compute it, where N is the total number of edges in both curves. We also present an O(N^2) algorithm to compute a locally correct discrete Fréchet matching.

  － BibTeX
  

  @article{locally-correct-fr-chet-matchings:2012,
      title = {Locally Correct Fréchet Matchings},
      author = {K. Buchin and M. Buchin and W. Meulemans and B. Speckmann},
      year = {2012},
      bookTitle = {20th European Symposium on Algorithms (ESA)},
  }
  

  [ PDF ]
  
• Locally Correct Fréchet Matchings
  K. Buchin, M. Buchin, W. Meulemans, and B. Speckmann.
  pp. 81—84, 2012.
  
  － Abstract
  

  The Fréchet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to "natural" matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such a matching exists for two polygonal curves and give an algorithm to compute it.

  － BibTeX
  

  @article{locally-correct-fr-chet-matchings:2012,
      title = {Locally Correct Fréchet Matchings},
      author = {K. Buchin and M. Buchin and W. Meulemans and B. Speckmann},
      year = {2012},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Four Soviets Walk the Dog, with an Application to Alt's Conjecture
  K. Buchin, M. Buchin, W. Meulemans, and W. Mulzer.
  2012.
  
  － Abstract
  

  Given two polygonal curves in the plane, there are several ways to define a measure of similarity between them. One measure that has been extremely popular in the past is the Frechet distance. Since it has been proposed by Alt and Godau in 1992, many variants and extensions have been described. However, even 20 years later, the original O(n^2 log n) algorithm by Alt and Godau for computing the Frechet distance remains the state of the art (here n denotes the number of vertices on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard. In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Frechet distance, where we consider sequences of points instead of polygonal curves. Building on their work, we give an algorithm to compute the Frechet distance between two polygonal curves in time O(n^2 (log n)^(1/2) (\log\log n)^(3/2)) on a pointer machine and in time O(n^2 (loglog n)^2) on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the Frechet problem of depth O(n^(2-epsilon)), for some epsilon &gt; 0. This provides evidence that computing the Frechet distance may not be 3SUM-hard after all and reveals an intriguing new aspect of this well-studied problem.

  － BibTeX
  

  @article{four-soviets-walk-the-dog-with-an-application-to-alt-s-conjecture:2012,
      title = {Four Soviets Walk the Dog, with an Application to Alt's Conjecture},
      author = {K. Buchin and M. Buchin and W. Meulemans and W. Mulzer},
      year = {2012},
      bookTitle = {},
  }
  

  [ PDF ]
  
• Locally Correct Fréchet Matchings
  K. Buchin, M. Buchin, W. Meulemans, and B. Speckmann.
  2012.
  
  － Abstract
  

  The Frechet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Frechet distance a Frechet matching. There are often many different Frechet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Frechet matchings to "natural" matchings and to this end introduce locally correct Frechet matchings. We prove that at least one such matching exists for two polygonal curves and give an O(N^3 log N) algorithm to compute it, where N is the total number of edges in both curves. We also present an O(N^2) algorithm to compute a locally correct discrete Frechet matching.

  － BibTeX
  

  @article{locally-correct-fr-chet-matchings:2012,
      title = {Locally Correct Fréchet Matchings},
      author = {K. Buchin and M. Buchin and W. Meulemans and B. Speckmann},
      year = {2012},
      bookTitle = {},
  }
  

  [ PDF ]
  

2011

• A New Method for Subdivision Simplification with Applications to Urban-Area Generalization
  K. Buchin, W. Meulemans, and B. Speckmann.
  19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM GIS), pp. 261—270, 2011.
  
  － Abstract
  

  We introduce a local operation for polygons and subdivisions called an edge-move. Edge-moves do not change the edge orientations present in the input and are thus suitable for iterative simplification or even schematization. Based on edge-moves we present a new efficient method for area- and topology-preserving subdivision simplification. We show how to tailor this generic method towards the specific needs of building wall squaring and urban-area generalization. Our algorithm is guaranteed to make further progress on any subdivision that has two or more faces and/or reflex vertices. Furthermore, our method produces output of high visual quality and is able to generalize maps with approximately 1.8 million edges in a few hours.

  － BibTeX
  

  @article{a-new-method-for-subdivision-simplification-with-applications-to-urban-area-generalization:2011,
      title = {A New Method for Subdivision Simplification with Applications to Urban-Area Generalization},
      author = {K. Buchin and W. Meulemans and B. Speckmann},
      year = {2011},
      bookTitle = {19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM GIS)},
  }
  

  [ PDF ]
  
• Delineating Imprecise Regions Via Shortest-Path Graphs
  M.T. Berg, de, W. Meulemans, and B. Speckmann.
  19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM GIS), pp. 271—280, 2011.
  
  － Abstract
  

  An imprecise region, also called a vernacular region, is a region without a precise or administrative boundary. We present a new method to delineate imprecise regions from a set of points that are likely to lie inside the region. We use shortest-path graphs based on the squared Euclidean distance which capture the shape of region boundaries well. Shortest-path graphs naturally adapt to point sets of varying density, and they are always connected. As opposed to neighborhood graphs, they use a non-local criterion to determine which points to connect. Furthermore, shortest- path graphs can easily be extended to take geographic context into account by modeling context as "soft" obstacles. We present efficient algorithms to compute shortest-path graphs with or without geographic context. We experimentally evaluate the quality of the imprecise regions computed with our method. To fairly compare our results to those obtained by the common KDE approach, we also show how to integrate context into KDE by again using soft obstacles.

  － BibTeX
  

  @article{delineating-imprecise-regions-via-shortest-path-graphs:2011,
      title = {Delineating Imprecise Regions Via Shortest-Path Graphs},
      author = {M.T. Berg, de and W. Meulemans and B. Speckmann},
      year = {2011},
      bookTitle = {19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM GIS)},
  }
  

  [ PDF ]
  
• Parallelity in Chorematic Territorial Outlines
  Andreas W. Reimer and W. Meulemans.
  Proceedings 14th ICA Workshop on Generalisation and Multiple Representation, pp. 1—12, 2011.
  
  － BibTeX
  

  @article{parallelity-in-chorematic-territorial-outlines:2011,
      title = {Parallelity in Chorematic Territorial Outlines},
      author = {Andreas W. Reimer and W. Meulemans},
      year = {2011},
      bookTitle = {Proceedings 14th ICA Workshop on Generalisation and Multiple Representation},
  }
  

  [ PDF ]
  
• Area-Preserving c-Oriented Schematization
  K. Buchin, W. Meulemans, and B. Speckmann.
  pp. 163—166, 2011.
  
  － Abstract
  

  We define an edge-move operation for polygons and prove that every simple non-convex polygon P has a non-conflicting pair of complementary edge-moves that reduces the number of edges of P while preserving its area. We use this result to generate area-preserving C-oriented schematizations of polygons.

  － BibTeX
  

  @article{area-preserving-c-oriented-schematization:2011,
      title = {Area-Preserving c-Oriented Schematization},
      author = {K. Buchin and W. Meulemans and B. Speckmann},
      year = {2011},
      bookTitle = {},
  }
  

  [ PDF ]
  

2010

• Area-Preserving Subdivision Schematization
  W. Meulemans, A.M. Renssen, van, and B. Speckmann.
  6th International Conference on Geographic Information Science (GIScience), pp. 160—174, 2010.
  
  － Abstract
  

  We describe an area-preserving subdivision schematization algorithm: the area of each region in the input equals the area of the corresponding region in the output. Our schematization is axis-aligned, the final output is a rectilinear subdivision. We first describe how to convert a given subdivision into an area-equivalent rectilinear subdivision. Then we define two area-preserving contraction operations and prove that at least one of these operations can always be applied to any given simple rectilinear polygon. We extend this approach to subdivisions and showcase experimental results. Finally, we give examples for standard distance metrics (symmetric difference, Hausdorff- and Fréchet-distance) that show that better schematizations might result in worse shapes.

  － BibTeX
  

  @article{area-preserving-subdivision-schematization:2010,
      title = {Area-Preserving Subdivision Schematization},
      author = {W. Meulemans and A.M. Renssen, van and B. Speckmann},
      year = {2010},
      bookTitle = {6th International Conference on Geographic Information Science (GIScience)},
  }
  

  [ PDF ]