Search

We study the following separation problem: Given a collection of pairwise disjoint coloured objects in the plane withkdifferent colours, compute a shortest “fence”F, i.e., a union of curves of minimum total length, that separates every pair of objects of different colours. Two objects are separated ifFcontains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem asgeometrick-cut, as it is a geometric analog to the well-studied multicut problem on graphs. We first give an$$O(n^4\log ^3\!n)$$O(n4log3n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colours withncorners in total. We then show that the problem is NP-hard for the case of three colours. Finally, we give a randomised$$4/3\cdot 1.2965$$4/3·1.2965-approximation algorithm for polygons and any number of colours.

Communicating the scientific data of the weather forecasts to the general public has always been a challenge. Using computer graphics’ visual representations to convey the message to television viewers and through weather apps and websites has certainly helped a lot to popularize the weather forecast consumption by the general public. However, these representations are not information rich since they are abstraction; moreover they are not always very actionable on the receiver side to help one decide how s/he will “live” the forecast weather conditions. Therefore, there is a need to personalize the forecast based on past user experience and personal needs. The forecast has to become more human- and needs-oriented and more focused to the particular requirements of each individual person. The challenge is to move from providing the abstraction of atmospheric information to a real sense of how the weather will "feel" to the individual.We therefore propose a new co-creation process in which the audience is called on to provide a daily feedback on how they lived the weather conditions personally, so that, “my personal forecast” can be produced making the forecast more actionable on the user side. Preliminary, but more personalized, such attempts include the “feels like” temperature forecasts. To arrive at the “my personal forecast”, AI-based recommender systems need to be applied, using fuzzy logic as the appropriate method for the user to express how s/he actually lived personally lived weather conditions every day. Over time this information can then be used to transform science-based descriptions of weather conditions into a sense of how the weather will be experienced at a personal level.

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time $2^{\tilde{O}(n^{2/3})}$ for \textsc{Maximum Clique} on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for \textsc{Max Clique} on disk and unit ball graphs. \textsc{Max Clique} on unit ball graphs is equivalent to finding, given a collection of points in $\mathbb R^3$, a maximum subset of points with diameter at most some fixed value. In stark contrast, \textsc{Maximum Clique} on ball graphs and unit $4$-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation which cannot be attained even in time $2^{n^{1-\varepsilon}}$, unless the Exponential Time Hypothesis fails., arXiv admin note: substantial text overlap with arXiv:1712.05010, arXiv:1803.01822

We study the complexity of the following cell connection problems in segment arrangements. Given a set of straight-line segments in the plane and two points [Formula: see text] and [Formula: see text] in different cells of the induced arrangement: [(i)] compute the minimum number of segments one needs to remove so that there is a path connecting [Formula: see text] to [Formula: see text] that does not intersect any of the remaining segments; [(ii)] compute the minimum number of segments one needs to remove so that the arrangement induced by the remaining segments has a single cell. We show that problems (i) and (ii) are NP-hard and discuss some special, tractable cases. Most notably, we provide a near-linear-time algorithm for a variant of problem (i) where the path connecting [Formula: see text] to [Formula: see text] must stay inside a given polygon [Formula: see text] with a constant number of holes, the segments are contained in [Formula: see text], and the endpoints of the segments are on the boundary of [Formula: see text]. The approach for this latter result uses homotopy of paths to group the segments into clusters with the property that either all segments in a cluster or none participate in an optimal solution.

We study the parameterized complexity of the k -center problem on a given n -point set P in ℝ d , with the dimension d as the parameter. We show that the rectilinear 3-center problem is fixed-parameter tractable, by giving an algorithm that runs in O ( n log n ) time for any fixed dimension d . On the other hand, we show that this is unlikely to be the case with both the Euclidean and rectilinear k -center problems for any k ≥ 2 and k ≥ 4 respectively. In particular, we prove that deciding whether P can be covered by the union of 2 balls of given radius or by the union of 4 cubes of given side length is W[1]-hard with respect to d , and thus not fixed-parameter tractable unless FPT=W[1]. For the Euclidean case, we also show that even an n o ( d ) -time algorithm does not exist, unless there is a 2 o ( n ) -time algorithm for n -variable 3SAT, that is, the Exponential Time Hypothesis fails.

We prove that computing a geometric minimum-dilation graph on a given set of points in the plane, using not more than a given number of edges, is an NP-hard problem, no matter if edge crossings are allowed or forbidden. We also show that the problem remains NP-hard even when a minimum-dilation tour or path is sought; not even an FPTAS exists in this case.

Given a Euclidean graph $G$ in $\mathbb{R}^d$ with $n$ vertices and $m$ edges, we consider the problem of adding an edge to $G$ such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a graph with positive edge weights runs in $\cal{O}$$(nm+n^2 \log n)$ time, resulting in a trivial $\cal{O}$$(n^3m+n^4 \log n)$-time algorithm for computing the optimal edge. First, we show that a simple modification yields the optimal solution in $\cal{O}$$(n^4)$ time using $\cal{O}$$(n^2)$ space. To reduce the running time we consider several approximation algorithms.

Deciding whether two n-point sets A, B ∈ℝ d are congruent is a fundamental problem in geometric pattern matching. When the dimension d is unbounded, the problem is equivalent to graph isomorphism and is conjectured to be in FPT.

This paper surveys parameterized complexity results for hard geometric algorithmic problems. It includes fixed-parameter tractable problems in graph drawing, geometric graphs, geometric covering and several other areas, together with an overview of the algorithmic techniques used. Fixed-parameter intractability results are surveyed as well. Finally, we give some directions for future research.

We study the following separation problem: given $$n$$n connected curves and two points $$s$$s and $$t$$t in the plane, compute the minimum number of curves one needs to retain so that any path connecting $$s$$s to $$t$$t intersects some of the retained curves. We give the first polynomial $$(\fancyscript{O}(n^3))$$(O(n3)) time algorithm for the problem, assuming that the curves have reasonable computational properties. The algorithm is based on considering the intersection graph of the curves, defining an appropriate family of closed walks in the intersection graph that satisfies the 3-path-condition, and arguing that a shortest cycle in the family gives an optimal solution. The 3-path-condition has been used mainly in topological graph theory, and thus its use here makes the connection to topology clear. We also show that the generalized version, where several input points are to be separated, is NP-hard for natural families of curves, like segments in two directions or unit circles.

The Erdős-Szekeres theorem states that, for every k, there is a number n k such that every set of n k points in general position in the plane contains a subset of k points in convex position. If we ask the same question for subsets whose convex hull does not contain any other point from the set, this is not true: as shown by Horton, there are sets of arbitrary size that do not contain an empty convex 7-gon.

International audience; The Discrete Milling problem is a natural and quite gen- eral graph-theoretic model for geometric milling problems: Given a graph, one asks for a walk that covers all its vertices with a minimum number of turns, as specified in the graph model by a 0/1 turncost function fx at each vertex x giving, for each ordered pair of edges (e, f ) incident at x, the turn cost at x of a walk that enters the vertex on edge e and departs on edge f . We describe an initial study of the parameterized complexity of the problem.

We study the following general stabbing problem from a parameterized complexity point of view: Given a set $\mathcal S$ of $n$ translates of an object in $\Rd$, find a set of $k$ lines with the property that every object in $\mathcal S$ is ''stabbed'' (intersected) by at least one line. We show that when $S$ consists of axis-parallel unit squares in $\Rtwo$ the (decision) problem of stabbing $S$ with axis-parallel lines is W[1]-hard with respect to $k$ (and thus, not fixed-parameter tractable unless FPT=W[1]) while it becomes fixed-parameter tractable when the squares are disjoint. We also show that the problem of stabbing a set of disjoint unit squares in $\Rtwo$ with lines of arbitrary directions is W[1]--hard with respect to $k$. Several generalizations to other types of objects and lines with arbitrary directions are also presented. Finally, we show that deciding whether a set of unit balls in $\Rd$ can be stabbed by one line is W[1]--hard with respect to the dimension $d$., Based on the MSc. Thesis of Daniel Werner, Free University Berlin, Berlin, Germany

Deciding whether two n-point sets A, B ∈ℝd are congruent is a fundamental problem in geometric pattern matching. When the dimension d is unbounded, the problem is equivalent to graph isomorphism and is conjectured to be in FPT. When |A|=m

The Earth Mover’s Distance (EMD) between two weighted point sets (point distributions) is a distance measure commonly used in computer vision for color-based image retrieval and shape matching. It measures the minimum amount of work needed to transform one set into the other one by weight transportation. We study the following shape matching problem: Given two weighted point sets A and B in the plane, compute a rigid motion of A that minimizes its Earth Mover’s Distance to B. No algorithm is known that computes an exact solution to this problem. We present simple FPTAS and polynomial-time (2 + e)-approximation algorithms for the minimum Euclidean EMD between A and B under translations and rigid motions.

We derive a pseudo-metric for weighted point sets. There are numerous situations, for example in the shape description domain, where the individual points in a feature point set have an associated attribute, a weight. A distance function that incorporates this extra information apart from the points' position can be very useful for matching and retrieval purposes. There are two main approaches to do this. One approach is to interpret the point sets as fuzzy sets. However, a distance measure for fuzzy sets that is a metric, invariant under rigid motion and respects scaling of the underlying ground distance, does not exist. In addition, a Hausdorff-like pseudo-metric fails to differentiate between fuzzy sets with arbitrarily different maximum memebership values. The other approach is the Earth Mover's Distance. However, for sets of unequal total weights, it gives zero distance for arbitrarily different sets, and does not obey the triangle inequality. In this paper we derive a distance measure, based on weight transportation, that is invariant under rigid motion, respects scaling, and obeys the triangle inequality, so that it can be used in efficient database searching. Moreover, our pseudo-metric identifies only weight-scaled versions of the same set. We demonstrate its potential use by testing it on two different collections, one of company logos and another one of fish contours.

Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. Depending on the ranges, several variants arise, including star discrepancy, box discrepancy, and discrepancy of halfspaces. These problems are solvable in time n^O^(^d^), where d is the dimension of the underlying space. As such a dependency on d becomes intractable for high-dimensional data, we ask whether it can be moderated. We answer this question negatively by proving that the canonical decision problems are W[1]-hard with respect to the dimension, implying that no f(d)@?n^O^(^1^)-time algorithm is possible for any function f(d) unless FPT=W[1]. We also discover the W[1]-hardness of other well known problems, such as determining the largest empty box that contains the origin and is inside the unit cube. This is shown to be hard even to approximate within a factor of 2^n.

The Earth Mover's Distance (EMD) between two weighted point sets (point distributions) is a distance measure commonly used in computer vision for color-based image retrieval and shape matching. It measures the minimum amount of work needed to transform one set into the other one by weight transportation. We study the following shape matching problem: Given two weighted point sets A and B in the plane, compute a rigid motion of A that minimizes its Earth Mover's Distance to B. No algorithm is known that computes an exact solution to this problem. We present simple FPTASs and polynomial-time ([email protected])-approximation algorithms for the minimum Euclidean EMD between A and B under translations and rigid motions.