An Optimal Algorithm to Compute the Inverse Beacon Attraction Region
Irina Kostitsyna, Bahram Kouhestani, Stefan Langerman, and David Rappaport.
arXiv,
2018.
－ Abstract
The beacon model is a recent paradigm for guiding the trajectory of messages or small robotic agents in complex environments. A beacon is a fixed point with an attraction pull that can move points within a given polygon. Points move greedily towards a beacon: if unobstructed, they move along a straight line to the beacon, and otherwise they slide on the edges of the polygon. The Euclidean distance from a moving point to a beacon is monotonically decreasing. A given beacon attracts a point if the point eventually reaches the beacon. The problem of attracting all points within a polygon with a set of beacons can be viewed as a variation of the art gallery problem. Unlike most variations, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. It is connected and can be computed in linear time for simple polygons. By contrast, it is known that the inverse attraction region of a point---the set of beacon positions that attract it---could have $\Omega(n)$ disjoint connected components. In this paper, we prove that, in spite of this, the total complexity of the inverse attraction region of a point in a simple polygon is linear, and present a $O(n \log n)$ time algorithm to construct it. This improves upon the best previous algorithm which required $O(n^3)$ time and $O(n^2)$ space. Furthermore we prove a matching $\Omega(n\log n)$ lower bound for this task in the algebraic computation tree model of computation, even if the polygon is monotone.
－ BibTeX
@article{an-optimal-algorithm-to-compute-the-inverse-beacon-attraction-region:2018,
title = {An Optimal Algorithm to Compute the Inverse Beacon Attraction Region},
author = {Irina Kostitsyna and Bahram Kouhestani and Stefan Langerman and David Rappaport},
year = {2018},
bookTitle = {arXiv},
}
[ PDF ]
Approximating $(K,\ell)$-Center Clustering for Curves
Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten Löffler, and Martijn Struijs.
arXiv,
2018.
－ Abstract
The Euclidean $k$-center problem is a classical problem that has been extensively studied in computer science. Given a set $\mathcal{G}$ of $n$ points in Euclidean space, the problem is to determine a set $\mathcal{C}$ of $k$ centers (not necessarily part of $\mathcal{G}$) such that the maximum distance between a point in $\mathcal{G}$ and its nearest neighbor in $\mathcal{C}$ is minimized. In this paper we study the corresponding $(k,\ell)$-center problem for polygonal curves under the Fr\'echet distance, that is, given a set $\mathcal{G}$ of $n$ polygonal curves in $\mathbb{R}^d$, each of complexity $m$, determine a set $\mathcal{C}$ of $k$ polygonal curves in $\mathbb{R}^d$, each of complexity $\ell$, such that the maximum Fr\'echet distance of a curve in $\mathcal{G}$ to its closest curve in $\mathcal{C}$ is minimized. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension $2$ and higher. We show that, if $\ell$ is part of the input, then there is no polynomial-time approximation scheme unless $\mathsf{P}=\mathsf{NP}$. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fr\'echet distance. In the case of the discrete Fr\'echet distance on two-dimensional curves, we show hardness of approximation within a factor close to $2.598$. This result also holds when $k=1$, and the $\mathsf{NP}$-hardness extends to the case that $\ell=\infty$, i.e., for the problem of computing the minimum-enclosing ball under the Fr\'echet distance. Finally, we observe that a careful adaptation of Gonzalez' algorithm in combination with a curve simplification yields a $3$-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.
－ BibTeX
@article{approximating-k-ell-center-clustering-for-curves:2018,
title = {Approximating $(K,\ell)$-Center Clustering for Curves},
author = {Kevin Buchin and Anne Driemel and Joachim Gudmundsson and Michael Horton and Irina Kostitsyna and Maarten Löffler and Martijn Struijs},
year = {2018},
bookTitle = {arXiv},
}
[ PDF ]
Colored Spanning Graphs for Set Visualization
F. Hurtado, M. Korman, M.J. van Kreveld, M. Löffler, V. Sacristán, A. Shioura, R.I. Silveira, B. Speckmann, and T. Tokuyama.
Computational Geometry,
68:262—276,
2018.
－ Abstract
<p>We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A red-blue-purple spanning graph (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected. We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem can be solved in polynomial time using matroid techniques. In addition, we discuss more efficient algorithms for the case in which points are located on a line or a circle, and also describe a fast ([Formula presented]ρ+1)-approximation algorithm, where ρ is the Steiner ratio.</p>
－ BibTeX
@article{colored-spanning-graphs-for-set-visualization:2018,
title = {Colored Spanning Graphs for Set Visualization},
author = {F. Hurtado and M. Korman and M.J. van Kreveld and M. Löffler and V. Sacristán and A. Shioura and R.I. Silveira and B. Speckmann and T. Tokuyama},
year = {2018},
bookTitle = {Computational Geometry},
}
[ PDF ]
Computing Nonsimple Polygons of Minimum Perimeter
S.P. Fekete, A. Haas, M. Hemmer, M. Hoffmann, I. Kostitsyna, D. Krupke, F. Maurer, J.S.B. Mitchell, A. Schmidt, C. Schmidt, and J. Troegel.
Journal of Computational Geometry,
8(1):340—365,
2018.
－ Abstract
We consider the Minimum Perimeter Polygon Problem (MP3): for a given set V of points in the plane, find a polygon P with holes that has vertex set V , such that the total boundary length is smallest possible. The MP3 can be considered a natural geometric generalization of the Traveling Salesman Problem (TSP), which asks for a simple polygon with minimum perimeter. Just like the TSP, the MP3 occurs naturally in the context of curve reconstruction. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MP3. On the positive side, we provide constant-factor approximation algorithms. In addition to algorithms with theoretical worst-case guarantess, we provide practical methods for computing provably optimal solutions for relatively large instances, based on integer programming. An additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that restricting the set of connections between points to edges of the Delaunay triangulation yields results that are on average within 0.5% of the optimum for large classes of benchmark instances. <br/><br/><br/><br/>
－ BibTeX
@article{computing-nonsimple-polygons-of-minimum-perimeter:2018,
title = {Computing Nonsimple Polygons of Minimum Perimeter},
author = {S.P. Fekete and A. Haas and M. Hemmer and M. Hoffmann and I. Kostitsyna and D. Krupke and F. Maurer and J.S.B. Mitchell and A. Schmidt and C. Schmidt and J. Troegel},
year = {2018},
bookTitle = {Journal of Computational Geometry},
}
[ PDF ]
Computing the Similarity Between Moving Curves
K. Buchin, T. Ophelders, and B. Speckmann.
Computational Geometry,
73:2—14,
2018.
－ Abstract
<p>In this paper we study similarity measures for moving curves which can, for example, model changing coastlines or retreating glacier termini. Points on a moving curve have two parameters, namely the position along the curve as well as time. We therefore focus on similarity measures for surfaces, specifically the Fréchet distance between surfaces. While the Fréchet distance between surfaces is generally NP-hard, we show for variants arising in the context of moving curves that they are polynomial-time solvable or NP-complete depending on the restrictions imposed on how the moving curves are matched. We achieve the polynomial-time solutions by a novel approach for computing a surface in the so-called free-space diagram based on a relation between obstacles.</p>
－ BibTeX
@article{computing-the-similarity-between-moving-curves:2018,
title = {Computing the Similarity Between Moving Curves},
author = {K. Buchin and T. Ophelders and B. Speckmann},
year = {2018},
bookTitle = {Computational Geometry},
}
[ PDF ]
Convex Hull Formation for Programmable Matter
Joshua J. Daymude, Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Christian Scheideler, and Andréa W. Richa.
arXiv,
2018.
－ Abstract
We envision programmable matter as a system of nano-scale agents (called particles) with very limited computational capabilities that move and compute collectively to achieve a desired goal. We use the geometric amoebot model as our computational framework, which assumes particles move on the triangular lattice. Motivated by the problem of shape sealing whose goal is to seal an object using as little resources as possible, we investigate how a particle system can self-organize to form an object's convex hull. We give a fully distributed, local algorithm for convex hull formation and prove that it runs in $\mathcal{O}(B + H\log H)$ asynchronous rounds, where $B$ is the length of the object's boundary and $H$ is the length of the object's convex hull. Our algorithm can be extended to also form the object's ortho-convex hull, which requires the same number of particles but additionally minimizes the enclosed space within the same asymptotic runtime.
－ BibTeX
@article{convex-hull-formation-for-programmable-matter:2018,
title = {Convex Hull Formation for Programmable Matter},
author = {Joshua J. Daymude and Robert Gmyr and Kristian Hinnenthal and Irina Kostitsyna and Christian Scheideler and Andréa W. Richa},
year = {2018},
bookTitle = {arXiv},
}
[ PDF ]
Convex Partial Transversals of Planar Regions
Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma.
arXiv,
2018.
－ Abstract
We consider the problem of testing, for a given set of planar regions $\cal R$ and an integer $k$, whether there exists a convex shape whose boundary intersects at least $k$ regions of $\cal R$. We provide a polynomial time algorithm for the case where the regions are disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.
－ BibTeX
@article{convex-partial-transversals-of-planar-regions:2018,
title = {Convex Partial Transversals of Planar Regions},
author = {Vahideh Keikha and Mees van de Kerkhof and Marc van Kreveld and Irina Kostitsyna and Maarten Löffler and Frank Staals and Jérôme Urhausen and Jordi L. Vermeulen and Lionov Wiratma},
year = {2018},
bookTitle = {arXiv},
}
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 ]
Homotopic c-Oriented Routing with Few Links and Thick Edges
B. Speckmann and K.A.B. Verbeek.
Computational Geometry,
67:11—28,
2018.
－ Abstract
<p>We study the NP-hard optimization problem of finding non-crossing thick C-oriented paths that are homotopic to a set of input paths in an environment with C-oriented obstacles, with the goal to minimize the total number of links of the paths. We introduce a special type of C-oriented paths—smooth paths—and present a 2-approximation algorithm for smooth paths that runs in O(n<sup>3</sup>logκ+k<sub>in</sub>logn+k<sub>out</sub>) time, where n is the total number of paths and obstacle vertices, k<sub>in</sub> and k<sub>out</sub> are the total complexities of the input and output paths, and κ=|C|. The algorithm also computes an O(κ)-approximation for general C-oriented paths. In particular we give a 2-approximation algorithm for rectilinear paths. Our algorithm not only approximates the minimum number of links, but also simultaneously minimizes the total length of the paths. As a related result we show that, given a set of (possibly crossing) C-oriented paths with a total of L links, non-crossing C-oriented paths homotopic to the input paths can require a total of Ω(Llogκ) links.</p>
－ BibTeX
@article{homotopic-c-oriented-routing-with-few-links-and-thick-edges:2018,
title = {Homotopic c-Oriented Routing with Few Links and Thick Edges},
author = {B. Speckmann and K.A.B. Verbeek},
year = {2018},
bookTitle = {Computational Geometry},
}
Improved Time-Space Trade-Offs for Computing Voronoi Diagrams
Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, A.M. van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein.
Journal of Computational Geometry,
9(1):191—212,
2018.
－ Abstract
Let $P$ be a planar set of $n$ \emph{sites} in general position.For $k \in \{1, \dots, n-1\}$, the Voronoi diagram\emph{of order $k$} for $P$ is obtained by subdividing the plane into\emph{cells} such that points in the same cell have the sameset of nearest $k$ neighbors in $P$.The \emph{\textup{(}nearest site\textup{)} Voronoi diagram} ($\NVD$) andthe\emph{farthest site Voronoi diagram} ($\FVD$) are the particular casesof $k=1$ and $k=n-1$, respectively. For any given $K \in \{1, \dots,n-1\}$, the family of all higher-order Voronoi diagrams of order$k = 1, \dots, K$ for $P$ can be computed in total time $O(nK^2+ n\log n)$ using $O(K^2(n-K))$ space [Aggarwal \etal, DCG'89; Lee, TC'82].Moreover, $\NVD$ and $\FVD$ for $P$ can be computed in $O(n\log n)$time using $O(n)$ space [Preparata, Shamos, Springer'85].<br/>For $s \in \{1, \dots, n\}$, an \emph{$s$-workspace} algorithm hasrandom access to a read-only array with the sites of $P$ in arbitraryorder. Additionally, the algorithm may use $O(s)$ words, of$\Theta(\log n)$ bits each, for reading and writing intermediate data.The output can be written only once and cannot be accessed ormodified afterwards.<br/>We describe a deterministic $s$-workspace algorithm for computing$\NVD$ and $\FVD$ for $P$ that runs in $O((n^2/s)\log s)$time. Moreover, we generalize our $s$-workspacealgorithm so that for any given $K \in O(\sqrt{s})$,we compute the family of all higher-order Voronoi diagramsof order $k = 1, \dots, K$ for $P$ in total expected time$O\bigl(\frac{n^2 K^5}{s}(\log s + K \, 2^{O(\log^* K)}) \bigr)$ orin total deterministic time$O\bigl(\frac{n^2 K^5}{s}(\log s + K \log K) \bigr)$.Previously, for Voronoi diagrams, the only known $s$-workspacealgorithm runs in \emph{expected} time$O\bigl((n^2/s) \log s + n \log s \log^*s\bigr)$ [Korman \etal, WADS'15]and only works for $\NVD$ (i.e., $k=1$). Unlike the previousalgorithm, our new method is very simple and does not rely onadvanced data structures or random sampling techniques.
－ BibTeX
@article{improved-time-space-trade-offs-for-computing-voronoi-diagrams:2018,
title = {Improved Time-Space Trade-Offs for Computing Voronoi Diagrams},
author = {Bahareh Banyassady and Matias Korman and Wolfgang Mulzer and A.M. van Renssen and Marcel Roeloffzen and Paul Seiferth and Yannik Stein},
year = {2018},
bookTitle = {Journal of Computational Geometry},
}
[ PDF ]
Line Segment Covering of Cells in Arrangements
Matias Korman, Sheung Hung Poon, and Marcel Roeloffzen.
Information Processing Letters,
129:25—30,
2018.
－ Abstract
<p>Given a collection L of line segments, we consider its arrangement and study the problem of covering all cells with line segments of L. That is, we want to find a minimum-size set L<sup>′</sup> of line segments such that every cell in the arrangement has a line from L<sup>′</sup> defining its boundary. We show that the problem is NP-hard, even when all segments are axis-aligned. In fact, the problem is still NP-hard when we only need to cover rectangular cells of the arrangement. For the latter problem we also show that it is fixed parameter tractable with respect to the size of the optimal solution. Finally we provide a linear time algorithm for the case where cells of the arrangement are created by recursively subdividing a rectangle using horizontal and vertical cutting segments.</p>
－ BibTeX
@article{line-segment-covering-of-cells-in-arrangements:2018,
title = {Line Segment Covering of Cells in Arrangements},
author = {Matias Korman and Sheung Hung Poon and Marcel Roeloffzen},
year = {2018},
bookTitle = {Information Processing Letters},
}
On Optimal Min-# Curve Simplification Problem
Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk.
arXiv,
2018.
－ Abstract
In this paper we consider the classical min--\# curve simplification problem in three different variants. Let $\delta>0$, $P$ be a polygonal curve with $n$ vertices in $\mathbb{R}^d$, and $D(\cdot,\cdot)$ be a distance measure. We aim to simplify $P$ by another polygonal curve $P'$ with minimum number of vertices satisfying $D(P,P') \leq \delta$. We obtain three main results for this problem: (1) An $O(n^4)$-time algorithm when $D(P,P')$ is the Fr\'echet distance and vertices in $P'$ are selected from a subsequence of vertices in $P$. (2) An NP-hardness result for the case that $D(P,P')$ is the directed Hausdorff distance from $P'$ to $P$ and the vertices of $P'$ can lie anywhere on $P$ while respecting the order of edges along $P$. (3) For any $\epsilon>0$, an $O^*(n^2\log n \log \log n)$-time algorithm that computes $P'$ whose vertices can lie anywhere in the space and whose Fr\'echet distance to $P$ is at most $(1+\epsilon)\delta$ with at most $2m+1$ links, where $m$ is the number of links in the optimal simplified curve and $O^*$ hides polynomial factors of $1/\epsilon$.
－ BibTeX
@article{on-optimal-min-curve-simplification-problem:2018,
title = {On Optimal Min-# Curve Simplification Problem},
author = {Mees van de Kerkhof and Irina Kostitsyna and Maarten Löffler and Majid Mirzanezhad and Carola Wenk},
year = {2018},
bookTitle = {arXiv},
}
[ PDF ]
Optimal Morphs of Planar Orthogonal Drawings
Arthur van Goethem and Kevin Verbeek.
arXiv,
2018.
－ Abstract
We describe an algorithm that morphs between two planar orthogonal drawings Γ_I and Γ_O of a connected graph G, while preserving planarity and orthogonality. Necessarily Γ_I and Γ_O share the same combinatorial embedding. Our morph uses a linear number of linear morphs (linear interpolations between two drawings) and preserves linear complexity throughout the process, thereby answering an open question from Biedl et al.<br/>Our algorithm first unifies the two drawings to ensure an equal number of (virtual) bends on each edge. We then interpret bends as vertices which form obstacles for so-called wires: horizontal and vertical lines separating the vertices of Γ_O. We can find corresponding wires in Γ_I that share topological properties with the wires in Γ_O. The structural difference between the two drawings can be captured by the spirality of the wires in Γ_I, which guides our morph from Γ_I to Γ_O.
－ BibTeX
@article{optimal-morphs-of-planar-orthogonal-drawings:2018,
title = {Optimal Morphs of Planar Orthogonal Drawings},
author = {Arthur van Goethem and Kevin Verbeek},
year = {2018},
bookTitle = {arXiv},
}
[ PDF ]
Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices
T. Bläsius, A. Karrer, and I. Rutter.
Algorithmica,
80(4):1214—1277,
2018.
－ Abstract
<p>A simultaneous embedding (with fixed edges) of two graphs G1 and G2 with common graph G=G1∩G2 is a pair of planar drawings of G1 and G2 that coincide on G. It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph G∪=G1∪G2, (2) most separating pairs of G
<sup>∪</sup>, and (3) connected components of G that are biconnected but not a cycle. Second, we give an O(n
<sup>3</sup>) -time algorithm solving Sefe for instances with the following restriction. Let u be a pole of a P-node μ in the SPQR-tree of a block of G1 or G2. Then at most three virtual edges of μ may contain common edges incident to u. All algorithms extend to the sunflower case, i.e., to the case of more than two graphs pairwise intersecting in the same common graph.
</p>
－ BibTeX
@article{simultaneous-embedding-edge-orderings-relative-positions-cutvertices:2018,
title = {Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices},
author = {T. Bläsius and A. Karrer and I. Rutter},
year = {2018},
bookTitle = {Algorithmica},
}
Simultaneous Visualization of Language Endangerment and Language Description
Harald Hammarström, T.H.A. Castermans, Robert Forkel, Kevin Verbeek, Michel A. Westenberg, and Bettina Speckmann.
Language Documentation & Conservation,
12:359—392,
2018.
－ Abstract
The world harbors a diversity of some 6,500 mutually unintelligible languages. As has been increasingly observed by linguists, many minority languages are becoming endangered and will be lost forever if not documented. Urgently indeed, many efforts are being launched to document and describe languages. This undertaking naturally has the priority toward the most endangered and least described languages. For the first time, we combine world-wide databases on language description (Glottolog) and language endangerment (ElCat, Ethnologue, UNESCO) and provide two online interfaces, GlottoScope and GlottoVis, to visualize these together. The interfaces are capable of browsing, filtering, zooming, basic statistics, and different ways of combining the two measures on a world map background. GlottoVis provides advanced techniques for combining cluttered dots on a map. With the tools and databases described we seek to increase the overall knowledge of the actual state language endangerment and description worldwide.
－ BibTeX
@article{simultaneous-visualization-of-language-endangerment-and-language-description:2018,
title = {Simultaneous Visualization of Language Endangerment and Language Description},
author = {Harald Hammarström and T.H.A. Castermans and Robert Forkel and Kevin Verbeek and Michel A. Westenberg and Bettina Speckmann},
year = {2018},
bookTitle = {Language Documentation & Conservation},
}
[ PDF ]
Stable Treemaps Via Local Moves
M. Sondag, B. Speckmann, and K.A.B. Verbeek.
IEEE Transactions on Visualization and Computer Graphics,
24(1):729—738,
2018.
－ Abstract
<p>Treemaps are a popular tool to visualize hierarchical data: items are represented by nested rectangles and the area of each rectangle corresponds to the data being visualized for this item. The visual quality of a treemap is commonly measured via the aspect ratio of the rectangles. If the data changes, then a second important quality criterion is the stability of the treemap: how much does the treemap change as the data changes. We present a novel stable treemapping algorithm that has very high visual quality. Whereas existing treemapping algorithms generally recompute the treemap every time the input changes, our algorithm changes the layout of the treemap using only local modifications. This approach not only gives us direct control over stability, but it also allows us to use a larger set of possible layouts, thus provably resulting in treemaps of higher visual quality compared to existing algorithms. We further prove that we can reach all possible treemap layouts using only our local modifications. Furthermore, we introduce a new measure for stability that better captures the relative positions of rectangles. We finally show via experiments on real-world data that our algorithm outperforms existing treemapping algorithms also in practice on either visual quality and/or stability. Our algorithm scores high on stability regardless of whether we use an existing stability measure or our new measure.</p>
－ BibTeX
@article{stable-treemaps-via-local-moves:2018,
title = {Stable Treemaps Via Local Moves},
author = {M. Sondag and B. Speckmann and K.A.B. Verbeek},
year = {2018},
bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
}
[ PDF ]
Table Cartogram
W. Evans, S. Felsner, M. Kaufmann, S.G. Kobourov, D. Mondal, R.I. Nishat, and K.A.B. Verbeek.
Computational Geometry,
68:174—185,
2018.
－ Abstract
<p>A table cartogram of a two dimensional m×n table A of non-negative weights in a rectangle R, whose area equals the sum of the weights, is a partition of R into convex quadrilateral faces corresponding to the cells of A such that each face has the same adjacency as its corresponding cell and has area equal to the cell's weight. Such a partition acts as a natural way to visualize table data arising in various fields of research. In this paper, we give a O(mn)-time algorithm to find a table cartogram in a rectangle. We then generalize our algorithm to obtain table cartograms inside arbitrary convex quadrangles, circles, and finally, on the surface of cylinders and spheres.</p>
－ BibTeX
@article{table-cartogram:2018,
title = {Table Cartogram},
author = {W. Evans and S. Felsner and M. Kaufmann and S.G. Kobourov and D. Mondal and R.I. Nishat and K.A.B. Verbeek},
year = {2018},
bookTitle = {Computational Geometry},
}
[ PDF ]
The Complexity of Snake and Undirected NCL Variants
Marzio De Biasi and T.A.E. Ophelders.
Theoretical Computer Science,
748:55—65,
2018.
－ Abstract
Snake and Nibbler are two well-known video games in which a snake slithers through a maze and grows as it collects food. During this process, the snake must avoid any collision with its tail. Various goals can be associated with these video games, such as avoiding the tail as long as possible, or collecting a certain amount of food, or reaching some target location. Unfortunately, like many other motion-planning problems, even very restricted variants are computationally intractable. In particular, we prove the NP-hardness of collecting all food on solid grid graphs; as well as its PSPACE-completeness on general grid graphs. Moreover, given an initial and a target configuration of the snake, moving from one configuration to the other is PSPACE-complete, even on grid graphs without food, or with an initially short snake.<br/>Our results make use of the nondeterministic constraint logic framework by Hearn and Demaine, which has been used to analyze the computational complexity of many games and puzzles. We extend this framework for the analysis of puzzles whose initial state is chosen by the player.<br/>
－ BibTeX
@article{the-complexity-of-snake-and-undirected-ncl-variants:2018,
title = {The Complexity of Snake and Undirected NCL Variants},
author = {Marzio De Biasi and T.A.E. Ophelders},
year = {2018},
bookTitle = {Theoretical Computer Science},
}
[ PDF ]
Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Art Galleries
F. Hoffmann, K. Kriegel, S. Suri, K.A.B. Verbeek, and M. Willert.
Computational Geometry,
73:24—34,
2018.
－ Abstract
The chromatic art gallery problem asks for the minimum number of "colors" t so that a collection of point guards, each assigned one of the t colors, can see the entire polygon subject to some conditions on the colors visible to each point. In this paper, we explore this problem for orthogonal polygons using orthogonal visibility-two points p and q are mutually visible if the smallest axis-aligned rectangle containing them lies within the polygon. Our main result establishes that for a conflict-free guarding of an orthogonal n-gon, in which at least one of the colors seen by every point is unique, the number of colors is in the worst case Θ(log log n). By contrast, the best known upper bound for orthogonal polygons under standard (non-orthogonal) visibility is O(log n) colors. We also show that the number of colors needed for strong guarding of simple orthogonal polygons, where all the colors visible to a point are unique, is, again in the worst case, Θ(log n). Finally, our techniques also help us establish the first non-trivial lower bound of Ω(log log n/log log log n) for conflict-free guarding under standard visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau.
－ BibTeX
@article{tight-bounds-for-conflict-free-chromatic-guarding-of-orthogonal-art-galleries:2018,
title = {Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Art Galleries},
author = {F. Hoffmann and K. Kriegel and S. Suri and K.A.B. Verbeek and M. Willert},
year = {2018},
bookTitle = {Computational Geometry},
}
Time-Space Trade-Offs for Triangulations and Voronoi Diagrams
Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein.
Computational Geometry,
73:35—45,
2018.
－ Abstract
<p>Let S be a planar n-point set. A triangulation for S is a maximal plane straight-line graph with vertex set S. The Voronoi diagram for S is the subdivision of the plane into cells such that all points in a cell have the same nearest neighbor in S. Classically, both structures can be computed in O(nlog n) time and O(n) space. We study the situation when the available workspace is limited: given a parameter s∈(1,...,n), an s-workspace algorithm has read-only access to an input array with the points from S in arbitrary order, and it may use only O(s) additional words of Θ(log n) bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic s-workspace algorithm for computing an arbitrary triangulation of S in time O(n2/s+nlog nlog s) and a randomized s-workspace algorithm for finding the Voronoi diagram of S in expected time O((n2/s)log s+nlog slog* s).</p>
－ BibTeX
@article{time-space-trade-offs-for-triangulations-and-voronoi-diagrams:2018,
title = {Time-Space Trade-Offs for Triangulations and Voronoi Diagrams},
author = {Matias Korman and Wolfgang Mulzer and André van Renssen and Marcel Roeloffzen and Paul Seiferth and Yannik Stein},
year = {2018},
bookTitle = {Computational Geometry},
}
[ PDF ]
BolVis: Visualization for Text-Based Research in Philosophy
Pauline van Wierst, Steven Hofstede, Yvette Oortwijn, T.H.A. Castermans, Rob Koopman, Shenghui Wang, Michel A. Westenberg, and Arianna Betti.
Proc. 3rd Workshop on Visualization for the Digital Humanities (VIS4DH),
2018.
－ Abstract
Traditional research in philosophy consists for a large part in conceptual analysis and close reading of texts. This is a precise but time-consuming approach, in which the researcher focuses on one particular text passage or one philosophical concept from one or more works of an author. In this paper, we present BolVis, a visualization tool for text-based research in philosophy. BolVis allows researchers to determine quickly which parts of a text corpus are most relevant for their research by performing a semantic similarity search on words, sentences, and passages. It supports activities such as filtering, exploring the semantic context, comparing, performing close reading on selected passages, et cetera. Our approach enables in-depth analysis of texts at a significantly greater scale than is possible by traditional means, thereby allowing researchers to gain in speed without compromising on precision. We demonstrate the usefulness of BolVis by applying it to a corpus consisting of about 11,000 pages of the writings of the Bohemian polymath Bernard Bolzano (1781--1848). Our use case addresses an open question about Bolzano's ideas concerning size equality for sets of natural numbers, and we show that the use of BolVis enabled us to find (at least a significant part of) the reason why he came to accept one-to-one correspondence as a sufficient criterion for size equality.
－ BibTeX
@article{bolvis-visualization-for-text-based-research-in-philosophy:2018,
title = {BolVis: Visualization for Text-Based Research in Philosophy},
author = {Pauline van Wierst and Steven Hofstede and Yvette Oortwijn and T.H.A. Castermans and Rob Koopman and Shenghui Wang and Michel A. Westenberg and Arianna Betti},
year = {2018},
bookTitle = {Proc. 3rd Workshop on Visualization for the Digital Humanities (VIS4DH)},
}
[ PDF ]
On Complexity and Efficiency of Mutual Information Estimation on Static and Dynamic Data
Michael Vollmer, Ignaz Rutter, and Klemens Böhm.
Advances in Database Technology - EDBT 2018,
pp. 49—60,
2018.
－ Abstract
<p>Mutual Information (MI) is an established measure for the dependence of two variables and is often used as a generalization of correlation measures. Existing methods to estimate MI focus on static data. However, dynamic data is ubiquitous as well, and MI estimates on it are useful for stream mining and advanced monitoring tasks. In dynamic data, small changes (e.g., insertion or deletion of a value) may often invalidate the previous estimate. In this article, we study how to efficiently adjust an existing MI estimate when such a change occurs. As a first step, we focus on the well-known nearest-neighbor based estimators for static data and derive a tight lower bound for their computational complexity, which is unknown so far. We then propose two dynamic data structures that can update existing estimates asymptotically faster than any approach that computes the estimates independently, i.e., from scratch. Next, we infer a lower bound for the computational complexity of such updates, irrespective of the data structure and the algorithm, and present an algorithm that is only a logarithmic factor slower than this bound. In absolute numbers, these solutions offer fast and accurate estimates of MI on dynamic data as well.</p>
－ BibTeX
@article{on-complexity-and-efficiency-of-mutual-information-estimation-on-static-and-dynamic-data:2018,
title = {On Complexity and Efficiency of Mutual Information Estimation on Static and Dynamic Data},
author = {Michael Vollmer and Ignaz Rutter and Klemens Böhm},
year = {2018},
bookTitle = {Advances in Database Technology - EDBT 2018},
}
[ PDF ]
On the Complexity of Optimal Homotopies
E.W. Chambers, A. de Mesmay, and T.A.E. Ophelders.
29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018,
pp. 1121—1134,
2018.
－ Abstract
<p>In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves 1 and ϵ on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between 1 and ϵ where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes and graph searching problems. We prove that Homotopy Height is in the complexity class NP, and the corresponding exponential algorithm is the best one known for this problem. This result builds on a structural theorem on monotonicity of optimal homotopies, which is proved in a companion paper. Then we show that this problem encompasses the Homotopic Fréchet distance problem which we therefore also establish to be in NP, answering a question which has previously been considered in several different settings. We also provide an O(log n)-approximation algorithm for Homotopy Height on surfaces by adapting an earlier algorithm of Har-Peled, Nayyeri, Salvatipour and Sidiropoulos in the planar setting.</p>
－ BibTeX
@article{on-the-complexity-of-optimal-homotopies:2018,
title = {On the Complexity of Optimal Homotopies},
author = {E.W. Chambers and A. de Mesmay and T.A.E. Ophelders},
year = {2018},
bookTitle = {29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018},
}
[ PDF ]
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 ]
Geometry and Topology of Estuary and Braided River Channel Networks Extracted from Topographic Data
Matthew Hiatt, Willem Sonke, Elisabeth Addink, Wout van Dijk, Marc J. van Kreveld, Tim Ophelders, Kevin Verbeek, Joyce Vlaming, Bettina Speckmann, and Maarten G. Kleinhans.
2018.
－ Abstract
Channels are ubiquitous features of Earth's surface that are important pathways for the transport of water, solids, and solutes across landscapes, provide a range of ecosystem services, and support economic activity. Networks are mathematical representations of the connections among a set of objects and are useful representations of topology, geometry, and connectivity in channelized environments. However, objective and automatic extraction of channel networks from topography in multi-channel systems like braided river and estuaries has remained elusive. We present a mathematically-rigorous framework from extracting network topology and geometry from digital elevation models (DEMs) of braided rivers and estuaries. The concept of the “sand function” is introduced, which quantifies the volume of material separating channels and is a useful metric for identifying the relative scales of channels in the network. Four case studies are included: DEMs from the Western Scheldt estuary (Netherlands) and the Waimakariri River (New Zealand), as well as DEMs generated by numerical models of the morphodynamics in a braided river and an estuary. We show that larger scale channels (with higher sand function values) in the estuaries tend to be significantly deeper than smaller scale channels in the network. The results suggest that the main channel in an estuary is significantly deeper than the rest of the network, while the braided rivers tend to have channel depths that are evenly-distributed across channel scales. In all cases, the length of channels relative to system size scales with sand function scale to the power of 0.24-0.35, while the number of nodes against system scale does not exhibit a power-law relationship. The methods and results presented in this study provide a benchmark for evaluating both geometric and topologic characteristics of multi-threaded channel networks across scales.
－ BibTeX
@article{geometry-and-topology-of-estuary-and-braided-river-channel-networks-extracted-from-topographic-data:2018,
title = {Geometry and Topology of Estuary and Braided River Channel Networks Extracted from Topographic Data},
author = {Matthew Hiatt and Willem Sonke and Elisabeth Addink and Wout van Dijk and Marc J. van Kreveld and Tim Ophelders and Kevin Verbeek and Joyce Vlaming and Bettina Speckmann and Maarten G. Kleinhans},
year = {2018},
bookTitle = {},
}
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 ]
Towards Hybrid Programmable Matter: Shape Recognition, Formation, and Sealing Algorithms for Finite Automaton Robots
Joshua Daymunde, Robert Gmyr, Kristian Hinnenthal, I. Kostitsyna, Fabian Kuhn, Andrea Richa, Dorian Rudolph, Christian Scheideler, and Thim Strothmann.
2018.
－ BibTeX
@article{towards-hybrid-programmable-matter-shape-recognition-formation-and-sealing-algorithms-for-finite-automaton-robots:2018,
title = {Towards Hybrid Programmable Matter: Shape Recognition, Formation, and Sealing Algorithms for Finite Automaton Robots},
author = {Joshua Daymunde and Robert Gmyr and Kristian Hinnenthal and I. Kostitsyna and Fabian Kuhn and Andrea Richa and Dorian Rudolph and Christian Scheideler and Thim Strothmann},
year = {2018},
bookTitle = {},
}
[ PDF ]