A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
Bart M.P. Jansen, Marcin Pilipczuk, and E.J. van Leeuwen.
arXiv,
2018.
－ Abstract
We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answers a question of Saurabh. On the way to these results, we provide an efficient sparsification routine in the flavor of the sparsification routine used for the Steiner Tree problem in planar graphs (FOCS 2014). It differs from the previous work because it preserves the existence of low-cost subgraphs that are not necessarily Steiner trees in the original plane graph, but structures that turn into (supergraphs of) Steiner trees after adding all edges between pairs of vertices that lie on a common face. We also show connections between Vertex Multiway Cut and the Vertex Planarization problem, where the existence of a polynomial kernel remains an important open problem.
－ BibTeX
@article{a-deterministic-polynomial-kernel-for-odd-cycle-transversal-and-vertex-multiway-cut-in-planar-graphs:2018,
title = {A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs},
author = {Bart M.P. Jansen and Marcin Pilipczuk and E.J. van Leeuwen},
year = {2018},
bookTitle = {arXiv},
}
[ PDF ]
An ETH-Tight Exact Algorithm for Euclidean TSP
Mark T. de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Sudeshna Kolay.
arXiv,
2018.
－ Abstract
We study exact algorithms for {\sc Euclidean TSP} in Rd. In the early 1990s algorithms with nO(n√) running time were presented for the planar case, and some years later an algorithm with nO(n1−1/d) running time was presented for any d≥2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on {\sc Euclidean TSP}, except for a lower bound stating that the problem admits no 2O(n1−1/d−ϵ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of {\sc Euclidean TSP} by giving a 2O(n1−1/d) algorithm and by showing that a 2o(n1−1/d) algorithm does not exist unless ETH fails.
－ BibTeX
@article{an-eth-tight-exact-algorithm-for-euclidean-tsp:2018,
title = {An ETH-Tight Exact Algorithm for Euclidean TSP},
author = {Mark T. de Berg and Hans L. Bodlaender and Sándor Kisfaludi-Bak and Sudeshna Kolay},
year = {2018},
bookTitle = {arXiv},
}
[ PDF ]
An Efficient Algorithm for the 1D Total Visibility-Index Problem and Its Parallelization
Peyman Afshani, Mark de Berg, Henri Casanova, Ben Karsin, Colin Lambrechts, Nodari Sitchinava, and Constantinos Tsirogiannis.
Journal on Experimental Algorithmics,
23(2):,
2018.
－ Abstract
<p>Let T be a terrain and P be a set of points on its surface. An important problem in Geographic Information Science (GIS) is computing the visibility index of a point p on P, that is, the number of points in P that are visible from p. The total visibility-index problem asks for the visibility index of every point in P. We present the first subquadratic-time algorithm to solve the one-dimensional total-visibility-index problem. Our algorithm uses a geometric dualization technique to reduce the problem to a set of instances of the red-blue line segment intersection counting problem, allowing us to find the total visibility-index in O(n log2 n) time. We implement a naive O(n2) approach and four variations of our algorithm: one that uses an existing red-blue line segment intersection counting algorithm and three new approaches that leverage features specific to our problem. Two of our implementations allow for parallel execution, requiringO(log2 n) time and O(n log2 n) work in the CREW PRAM model. We present experimental results for both serial and parallel implementations on synthetic and real-world datasets using two hardware platforms. Results show that all variants of our algorithm outperform the naive approach by several orders of magnitude. Furthermore, we show that our special-case red-blue line segment intersection counting implementations out-perform the existing general-case solution by up to a factor 10. Our fastest parallel implementation is able to process a terrain of more than 100 million vertices in under 3 minutes, achieving up to 85% parallel efficiency using 16 cores.</p>
－ BibTeX
@article{an-efficient-algorithm-for-the-1d-total-visibility-index-problem-and-its-parallelization:2018,
title = {An Efficient Algorithm for the 1D Total Visibility-Index Problem and Its Parallelization},
author = {Peyman Afshani and Mark de Berg and Henri Casanova and Ben Karsin and Colin Lambrechts and Nodari Sitchinava and Constantinos Tsirogiannis},
year = {2018},
bookTitle = {Journal on Experimental Algorithmics},
}
[ PDF ]
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 ]
Approximation and Kernelization for Chordal Vertex Deletion
Bart M.P. Jansen and Marcin Pilipczuk.
SIAM Journal on Discrete Mathematics,
32(3):2258—2301,
2018.
－ Abstract
<p>The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by the solution size. Using a new Erdos-Posa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of ChVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [D. Marx, ``Chordal Deletion Is Fixed-Parameter Tractable,"" in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37--48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for ChVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size \scrO (k<sup>4</sup> log<sup>2</sup> k).</p>
－ BibTeX
@article{approximation-and-kernelization-for-chordal-vertex-deletion:2018,
title = {Approximation and Kernelization for Chordal Vertex Deletion},
author = {Bart M.P. Jansen and Marcin Pilipczuk},
year = {2018},
bookTitle = {SIAM Journal on Discrete Mathematics},
}
[ PDF ]
Best-Case and Worst-Case Sparsifiability of Boolean CSPs
Hubie Chen, Bart M.P. Jansen, and Astrid Pieterse.
arXiv,
2018.
－ Abstract
We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, such that a bound on the number of resulting constraints can be given in terms of the number of variables n. We investigate how the worst-case sparsification size depends on the types of constraints allowed in the problem formulation (the constraint language). Two algorithmic results are presented. The first result essentially shows that for any arity k, the only constraint type for which no nontrivial sparsification is possible has exactly one falsifying assignment, and corresponds to logical OR (up to negations). Our second result concerns linear sparsification, that is, a reduction to an equivalent instance with O(n) constraints. Using linear algebra over rings of integers modulo prime powers, we give an elegant necessary and sufficient condition for a constraint type to be captured by a degree-1 polynomial over such a ring, which yields linear sparsifications. The combination of these algorithmic results allows us to prove two characterizations that capture the optimal sparsification sizes for a range of Boolean CSPs. For NP-complete Boolean CSPs whose constraints are symmetric (the satisfaction depends only on the number of 1 values in the assignment, not on their positions), we give a complete characterization of which constraint languages allow for a linear sparsification. For Boolean CSPs in which every constraint has arity at most three, we characterize the optimal size of sparsifications in terms of the largest OR that can be expressed by the constraint language.
－ BibTeX
@article{best-case-and-worst-case-sparsifiability-of-boolean-csps:2018,
title = {Best-Case and Worst-Case Sparsifiability of Boolean CSPs},
author = {Hubie Chen and Bart M.P. Jansen and Astrid Pieterse},
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 Chromatic Number Using Graph Decompositions Via Matrix Rank
Bart M.P. Jansen and Jesper Nederlof.
arXiv,
2018.
－ Abstract
Computing the smallest number q such that the vertices of a given graph can be properly q-colored is one of the oldest and most fundamental problems in combinatorial optimization. The q-Coloring problem has been studied intensively using the framework of parameterized algorithmics, resulting in a very good understanding of the best-possible algorithms for several parameterizations based on the structure of the graph. While there is an abundance of work for parameterizations based on decompositions of the graph by vertex separators, almost nothing is known about parameterizations based on edge separators. We fill this gap by studying q-Coloring parameterized by cutwidth, and parameterized by pathwidth in bounded-degree graphs. Our research uncovers interesting new ways to exploit small edge separators.<br/>We present two algorithms for q-Coloring parameterized by cutwidth cutw: a deterministic one that runs in time O∗(2ω⋅cutw), where ω is the matrix multiplication constant, and a randomized one with runtime O∗(2cutw). In sharp contrast to earlier work, the running time is independent of q. The dependence on cutwidth is optimal: we prove that even 3-Coloring cannot be solved in O∗((2−ε)cutw) time assuming the Strong Exponential Time Hypothesis (SETH). Our algorithms rely on a new rank bound for a matrix that describes compatible colorings. Combined with a simple communication protocol for evaluating a product of two polynomials, this also yields an O∗((⌊d/2⌋+1)pw) time randomized algorithm for q-Coloring on graphs of pathwidth pw and maximum degree d. Such a runtime was first obtained by Björklund, but only for graphs with few proper colorings. We also prove that this result is optimal in the sense that no O∗((⌊d/2⌋+1−ε)pw)-time algorithm exists assuming SETH.
－ BibTeX
@article{computing-the-chromatic-number-using-graph-decompositions-via-matrix-rank:2018,
title = {Computing the Chromatic Number Using Graph Decompositions Via Matrix Rank},
author = {Bart M.P. Jansen and Jesper Nederlof},
year = {2018},
bookTitle = {arXiv},
}
[ 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 ]
Faster Algorithms for Computing Plurality Points
Mark T. de Berg, Joachim Gudmundsson, and Mehran Mehr.
ACM Transactions on Algorithms,
14(3):,
2018.
－ Abstract
<p>Let V be a set of n points in R
<sup>d</sup>, which we call voters. A point p ∈ R
<sup>d</sup> is preferred over another point p' ∈ R
<sup>d</sup> by a voter v ∈ V if dist(v, p) < dist(v, p'). A point p is called a plurality point if it is preferred by at least as many voters as any other point p'. We present an algorithm that decides in O(n log n) time whether V admits a plurality point in the L
<sub>2</sub> norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute a minimum-cost subset W ⊂ V such that V \ W admits a plurality point, and to compute a so-called minimum-radius plurality 6 ball. Finally, we consider the problem in the personalized L
<sub>1</sub> norm, where each point v ∈ V has a preference vector w
<sub>1</sub> (v), . . ., w
<sub>d</sub> (v) and the distance from v to any point p ∈ R
<sup>d</sup> is given by
<sup>d</sup>
<sub>i</sub>=
<sub>1</sub> w
<sub>i</sub> (v) · |x
<sub>i</sub> (v) − x
<sub>i</sub> (p) |. For this case we can compute in O(n
<sup>d</sup>
<sup>−1</sup> ) time the set of all plurality points of V. When all preference vectors are equal, the running time improves to O(n).
</p>
－ BibTeX
@article{faster-algorithms-for-computing-plurality-points:2018,
title = {Faster Algorithms for Computing Plurality Points},
author = {Mark T. de Berg and Joachim Gudmundsson and Mehran Mehr},
year = {2018},
bookTitle = {ACM Transactions on Algorithms},
}
[ PDF ]
Finding Pairwise Intersections Inside a Query Range
Mark T. de Berg, Joachim Gudmundsson, and A. Mehrabi Davoodabadi.
Algorithmica,
80(11):3253—3269,
2018.
－ Abstract
We study the following problem: preprocess a set O of objects into a data structure that allows us to efficiently report all pairs of objects from O that intersect inside an axis-aligned query range Q . We present data structures of size O(n⋅polylogn) and with query time O((k+1)⋅polylogn) time, where k is the number of reported pairs, for two classes of objects in R2 : axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in R3 , we present a data structure of size O(nn−−√⋅polylogn) and query time O((n−−√+k)⋅polylogn) . When the objects and query are fat, we obtain O((k+1)⋅polylogn) query time using O(n⋅polylogn) storage.
－ BibTeX
@article{finding-pairwise-intersections-inside-a-query-range:2018,
title = {Finding Pairwise Intersections Inside a Query Range},
author = {Mark T. de Berg and Joachim Gudmundsson and A. Mehrabi Davoodabadi},
year = {2018},
bookTitle = {Algorithmica},
}
[ PDF ]
Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden.
arXiv,
pp. 1—38,
2018.
－ Abstract
We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time $2^{O(n^{1-1/d})}$ for any fixed dimension $d \geq 2$ for many well known graph problems, including Independent Set, $r$-Dominating Set for constant $r$, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms work on the graph itself, i.e., do not require any geometric information. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques. The lower bound framework is based on a constructive embedding of graphs into d-dimensional grids, and it allows us to derive matching $2^{\Omega(n^{1-1/d})}$ lower bounds under the Exponential Time Hypothesis even in the much more restricted class of $d$-dimensional induced grid graphs.
－ BibTeX
@article{framework-for-eth-tight-algorithms-and-lower-bounds-in-geometric-intersection-graphs:2018,
title = {Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs},
author = {Mark de Berg and Hans L. Bodlaender and Sándor Kisfaludi-Bak and Dániel Marx and Tom C. van der Zanden},
year = {2018},
bookTitle = {arXiv},
}
[ PDF lock ]
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 ]
Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes
Mark de Berg, Bart M.P. Jansen, and Debankur Mukherjee.
Discrete Applied Mathematics,
250:165—182,
2018.
－ Abstract
<p>Traditionally, reconfiguration problems ask the question whether a given solution of an optimization problem can be transformed to a target solution in a sequence of small steps that preserve feasibility of the intermediate solutions. In this paper, rather than asking this question from an algorithmic perspective, we analyze the combinatorial structure behind it. We consider the problem of reconfiguring one independent set into another, using two different processes: (1) exchanging exactly [Formula presented] vertices in each step, or (2) removing or adding one vertex in each step while ensuring the intermediate sets contain at most [Formula presented] fewer vertices than the initial solution. We are interested in determining the minimum value of [Formula presented] for which this reconfiguration is possible, and bound these threshold values in terms of several structural graph parameters. For hereditary graph classes we identify structures that cause the reconfiguration threshold to be large.</p>
－ BibTeX
@article{independent-set-reconfiguration-thresholds-of-hereditary-graph-classes:2018,
title = {Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes},
author = {Mark de Berg and Bart M.P. Jansen and Debankur Mukherjee},
year = {2018},
bookTitle = {Discrete Applied Mathematics},
}
[ 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},
}
Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
B.A.M. van Geffen, Bart M.P. Jansen, Arnoud A.W.M. de Kroon, and Rolf Morel.
arXiv,
2018.
－ Abstract
Many combinatorial problems can be solved in time O∗(ctw) on graphs of treewidth tw, for a problem-specific constant c. In several cases, matching upper and lower bounds on c are known based on the Strong Exponential Time Hypothesis (SETH). In this paper we investigate the complexity of solving problems on graphs of bounded cutwidth, a graph parameter that takes larger values than treewidth. We strengthen earlier treewidth-based lower bounds to show that, assuming SETH, Independent Set cannot be solved in O∗((2−ε)cutw) time, and Dominating Set cannot be solved in O∗((3−ε)cutw) time. By designing a new crossover gadget, we extend these lower bounds even to planar graphs of bounded cutwidth or treewidth. Hence planarity does not help when solving Independent Set or Dominating Set on graphs of bounded width. This sharply contrasts the fact that in many settings, planarity allows problems to be solved much more efficiently.
－ BibTeX
@article{lower-bounds-for-dynamic-programming-on-planar-graphs-of-bounded-cutwidth:2018,
title = {Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth},
author = {B.A.M. van Geffen and Bart M.P. Jansen and Arnoud A.W.M. de Kroon and Rolf Morel},
year = {2018},
bookTitle = {arXiv},
}
[ PDF ]
Non-Monochromatic and Conflict-Free Coloring on Tree Spaces and Planar Network Spaces
Boris Aronov, Mark T. de Berg, Aleksandar Markovic, and Gerhard J. Woeginger.
arXiv,
2018.
－ Abstract
It is well known that any set of n intervals in R1 admits a non-monochromatic coloring with two colors and a conflict-free coloring with three colors. We investigate generalizations of this result to colorings of objects in more complex 1-dimensional spaces, namely so-called tree spaces and planar network spaces.
－ BibTeX
@article{non-monochromatic-and-conflict-free-coloring-on-tree-spaces-and-planar-network-spaces:2018,
title = {Non-Monochromatic and Conflict-Free Coloring on Tree Spaces and Planar Network Spaces},
author = {Boris Aronov and Mark T. de Berg and Aleksandar Markovic and Gerhard J. Woeginger},
year = {2018},
bookTitle = {arXiv},
}
[ PDF ]
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 ]
Parallel Machine Scheduling with a Single Resource Per Job
Teun Janssen, Céline Swennenhuis, Abdoul Bitar, Thomas Bosman, Dion Gijswijt, Leo van Iersel, Stéphane Dauzère-Pérès, and Claude Yugma.
arXiv,
2018:,
2018.
－ Abstract
We study the problem of scheduling jobs on parallel machines minimizing the total completion time, with each job using exactly one resource. First, we derive fundamental properties of the problem and show that the problem is polynomially solvable if pj=1. Then we look at a variant of the shortest processing time rule as an approximation algorithm for the problem and show that it gives at least a (2−1m)-approximation. Subsequently, we show that, although the complexity of the problem remains open, three related problems are NP-hard. In the first problem, every resource also has a subset of machines on which it can be used. In the second problem, once a resource has been used on a machine it cannot be used on any other machine, hence all jobs using the same resource need to be scheduled on the same machine. In the third problem, every job needs exactly two resources instead of just one.
－ BibTeX
@article{parallel-machine-scheduling-with-a-single-resource-per-job:2018,
title = {Parallel Machine Scheduling with a Single Resource Per Job},
author = {Teun Janssen and Céline Swennenhuis and Abdoul Bitar and Thomas Bosman and Dion Gijswijt and Leo van Iersel and Stéphane Dauzère-Pérès and Claude Yugma},
year = {2018},
bookTitle = {arXiv},
}
[ PDF ]
Polynomial Kernels for Hitting Forbidden Minors Under Structural Parameterizations
Bart M.P. Jansen and Astrid Pieterse.
arXiv,
2018.
－ Abstract
We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graphs F, the F-Deletion problem is the following: given a graph G and integer k, is it possible to delete k vertices from G to ensure the resulting graph does not contain any graph from F as a minor? Earlier work by Fomin, Lokshtanov, Misra, and Saurabh [FOCS'12] showed that when F contains a planar graph, an instance (G,k) can be reduced in polynomial time to an equivalent one of size kO(1). In this work we focus on structural measures of the complexity of an instance, with the aim of giving nontrivial preprocessing guarantees for instances whose solutions are large. Motivated by several impossibility results, we parameterize the F-Deletion problem by the size of a vertex modulator whose removal results in a graph of constant treedepth η.<br/>We prove that for each set F of connected graphs and constant η, the F-Deletion problem parameterized by the size of a treedepth-η modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or well-quasi-ordering, which are sources of algorithmic non-constructivity in earlier works on F-Deletion. Our main technical contribution is to analyze how models of a forbidden minor in a graph G with modulator X, interact with the various connected components of G-X. By bounding the number of different types of behavior that can occur by a polynomial in |X|, we obtain a polynomial kernel using a recursive preprocessing strategy. Our results extend earlier work for specific instances of F-Deletion such as Vertex Cover and Feedback Vertex Set. It also generalizes earlier preprocessing results for F-Deletion parameterized by a vertex cover, which is a treedepth-one modulator.
－ BibTeX
@article{polynomial-kernels-for-hitting-forbidden-minors-under-structural-parameterizations:2018,
title = {Polynomial Kernels for Hitting Forbidden Minors Under Structural Parameterizations},
author = {Bart M.P. Jansen and Astrid Pieterse},
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 ]
Polynomial Kernels for Hitting Forbidden Minors Under Structural Parameterizations
Bart M.P. Jansen and Astrid Pieterse.
26th European Symposium on Algorithms, ESA 2018,
2018.
－ Abstract
<p>We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of graphs F, the F-DELETION problem is the following: given a graph G and integer k, is it possible to delete k vertices from G to ensure the resulting graph does not contain any graph from F as a minor? Earlier work by Fomin, Lokshtanov, Misra, and Saurabh [FOCS'12] showed that when F contains a planar graph, an instance (G, k) can be reduced in polynomial time to an equivalent one of size <sup>kO(1)</sup>. In this work we focus on structural measures of the complexity of an instance, with the aim of giving nontrivial preprocessing guarantees for instances whose solutions are large. Motivated by several impossibility results, we parameterize the F-DELETION problem by the size of a vertex modulator whose removal results in a graph of constant treedepth η. We prove that for each set F of connected graphs and constant η, the F-DELETION problem parameterized by the size of a treedepth-η modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or well-quasi-ordering, which are sources of algorithmic non-constructivity in earlier works on F-DELETION. Our main technical contribution is to analyze how models of a forbidden minor in a graph G with modulator X, interact with the various connected components of G - X. Using the language of labeled minors, we analyze the fragments of potential forbidden minor models that can remain after removing an optimal F-DELETION solution from a single connected component of G - X. By bounding the number of different types of behavior that can occur by a polynomial in |X|, we obtain a polynomial kernel using a recursive preprocessing strategy. Our results extend earlier work for specific instances of F-DELETION such as VERTEX COVER and FEEDBACK VERTEX SET. It also generalizes earlier preprocessing results for F-DELETION parameterized by a vertex cover, which is a treedepth-one modulator.</p>
－ BibTeX
@article{polynomial-kernels-for-hitting-forbidden-minors-under-structural-parameterizations:2018,
title = {Polynomial Kernels for Hitting Forbidden Minors Under Structural Parameterizations},
author = {Bart M.P. Jansen and Astrid Pieterse},
year = {2018},
bookTitle = {26th European Symposium on Algorithms, ESA 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 ]
