Search

We study a budget-aggregation setting in which a number of voters report their ideal distribution of a budget over a set of alternatives, and a mechanism aggregates these reports into an allocation. Ideally, such mechanisms are truthful, i.e., voters should not be incentivized to misreport their preferences. For the case of two alternatives, the set of mechanisms that are truthful and additionally meet a range of basic desiderata (anonymity, neutrality, and continuity) exactly coincides with the so-called moving-phantom mechanisms, but whether this space is richer for more alternatives was repeatedly stated as an open question. We answer this question in the affirmative by presenting a class of truthful mechanisms that are not moving-phantoms but satisfy the three properties. Since moving-phantom mechanisms can only provide limited fairness guarantees (measured as the worst-case distance to a fair share solution), one motivation for broadening the class of truthful mechanisms is the hope for improved fairness guarantees. We dispel this hope by showing that lower bounds holding for the class of moving-phantom mechanisms extend to all truthful, anonymous, neutral, and continuous mechanisms.

Let $\mathcal{P}$ be a simple polygon with $m$ vertices and let $P$ be a set of $n$ points inside $\mathcal{P}$. We prove that there exists, for any $\varepsilon>0$, a set $\mathcal{C} \subset P$ of size $O(1/\varepsilon^2)$ such that the following holds: for any query point $q$ inside the polygon $\mathcal{P}$, the geodesic distance from $q$ to its furthest neighbor in $\mathcal{C}$ is at least $1-\varepsilon$ times the geodesic distance to its further neighbor in $P$. Thus the set $\mathcal{C}$ can be used for answering $\varepsilon$-approximate furthest-neighbor queries with a data structure whose storage requirement is independent of the size of $P$. The coreset can be constructed in $O\left(\frac{1}{\varepsilon} \left( n\log(1/\varepsilon) + (n+m)\log(n+m)\right) \right)$ time., Comment: To appear in SoCG 2024

Let $d$ be a (well-behaved) shortest-path metric defined on a path-connected subset of $\mathbb{R}^2$ and let $\mathcal{D}=\{D_1,\ldots,D_n\}$ be a set of geodesic disks with respect to the metric $d$. We prove that $\mathcal{G}^{\times}(\mathcal{D})$, the intersection graph of the disks in $\mathcal{D}$, has a clique-based separator consisting of $O(n^{3/4+\varepsilon})$ cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for $q$-COLORING that runs in time $2^{O(n^{3/4+\varepsilon})}$, assuming the boundaries of the disks $D_i$ can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses $O(n^{7/4+\varepsilon})$ storage and can report the hop distance between any two nodes in $\mathcal{G}^{\times}(\mathcal{D})$ in $O(n^{3/4+\varepsilon})$ time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes., Comment: The paper will appear in SoCG 2024

Recently, many studies have been devoted to finding diverse solutions in classical combinatorial problems, such as Vertex Cover (Baste et al., IJCAI'20), Matching (Fomin et al., ISAAC'20) and Spanning Tree (Hanaka et al., AAAI'21). We initiate the algorithmic study of $k$-Diverse Minimum s-t Cuts which, given a directed graph $G = (V, E)$, two specified vertices $s,t \in V$, and an integer $k > 0$, asks for a collection of $k$ minimum $s$-$t$ cuts in $G$ that has maximum diversity. We investigate the complexity of the problem for maximizing three diversity measures that can be applied to a collection of cuts: (i) the sum of all pairwise Hamming distances, (ii) the cardinality of the union of cuts in the collection, and (iii) the minimum pairwise Hamming distance. We prove that $k$-Diverse Minimum s-t Cuts can be solved in strongly polynomial time for diversity measures (i) and (ii) via submodular function minimization. We obtain this result by establishing a connection between ordered collections of minimum $s$-$t$ cuts and the theory of distributive lattices. When restricted to finding only collections of mutually disjoint solutions, we provide a more practical algorithm that finds a maximum set of pairwise disjoint minimum $s$-$t$ cuts. For graphs with small minimum $s$-$t$ cut, it runs in the time of a single max-flow computation. Our results stand in contrast to the problem of finding $k$ diverse global minimum cuts -- which is known to be NP-hard even for the disjoint case (Hanaka et al., AAAI'23) -- and partially answer a long-standing open question of Wagner (Networks, 1990) about improving the complexity of finding disjoint collections of minimum $s$-$t$ cuts. Lastly, we show that $k$-Diverse Minimum s-t Cuts subject to diversity measure (iii) is NP-hard already for $k=3$., Comment: An earlier version of this work appeared at the 34th International Symposium on Algorithms and Computation (ISAAC 2023). Corrected typos in Section 3 and revised arguments in Section 4. Results unchanged. Added new complexity results in Section 5. Readded missing acknowledgments section

Given a point set $P \subseteq X$ of size $n$ in a metric space $(X,dist)$ of doubling dimension $d$ and two parameters $k \in N$ and $z \in N$, the $k$-center problem with $z$ outliers asks to return a set $C^\ast \subseteq X$ of $k$ centers such that the maximum distance of all but $z$ points of $P$ to their nearest center in $C^\ast$ is minimized. An $(\epsilon,k,z)$-coreset for this problem is a weighted point set $P^*$ such that an optimal solution for the $k$-center problem with $z$ outliers on $P^*$ gives a $(1\pm\epsilon)$-approximation for the $k$-center problem with $z$ outliers on $P$. We study the construction of such coresets in the Massively Parallel Computing (MPC) model, and in the insertion-only as well as the fully dynamic streaming model. We obtain the following results, for any given $0 < \epsilon \le 1$: In all cases, the size of the computed coreset is $O(k/\epsilon^d+z)$. - In the MPC model, we present a deterministic $2$-round and a randomized $1$-round algorithm. Additionally, we provide a deterministic algorithm that obtains a trade-off between the number of rounds, $R$, and the storage per machine. - For the insertion-only streaming model, we present an algorithm and a tight lower bound to support it. - We also discuss the dynamic streaming model, which allows both insertions and deletions in the data stream. In this model, we present the first algorithm and a lower bound. - Finally, we consider the sliding window model, where we are interested in maintaining an $(\epsilon,k,z)$-coreset for the last $W$ points in the stream, we present a tight lower bound that confirms the optimality of the previous work by De Berg, Monemizadeh, and Zhong (ESA2020).

Let $P$ be a set of $n$ points in the plane, where each point $p\in P$ has a transmission radius $r(p)>0$. The transmission graph defined by $P$ and the given radii, denoted by $\mathcal{G}_{\mathrm{tr}}(P)$, is the directed graph whose nodes are the points in $P$ and that contains the arcs $(p,q)$ such that $|pq|\leq r(p)$. An and Oh [Algorithmica 2022] presented a reachability oracle for transmission graphs. Their oracle uses $O(n^{5/3})$ storage and, given two query points $s,t\in P$, can decide in $O(n^{2/3})$ time if there is a path from $s$ to $t$ in $\mathcal{G}_{\mathrm{tr}}(P)$. We show that the clique-based separators introduced by De Berg \emph{et al.} [SICOMP 2020] can be used to improve the storage of the oracle to $O(n\sqrt{n})$ and the query time to $O(\sqrt{n})$. Our oracle can be extended to approximate distance queries: we can construct, for a given parameter $\varepsilon>0$, an oracle that uses $O((n/\varepsilon)\sqrt{n}\log n)$ storage and that can report in $O((\sqrt{n}/\varepsilon)\log n)$ time a value $d_{\mathrm{hop}}^*(s,t)$ satisfying $d_{\mathrm{hop}}(s,t) \leq d_{\mathrm{hop}}^*(s,t) < (1+\varepsilon)\cdot d_{\mathrm{hop}}(s,t) + 1$, where $d_{\mathrm{hop}}(s,t)$ is the hop-distance from $s$ to $t$. We also show how to extend the oracle to so-called continuous queries, where the target point $t$ can be any point in the plane. To obtain an efficient preprocessing algorithm, we show that a clique-based separator of a set~$F$ of convex fat objects in $\Bbb{R}^d$ can be constructed in $O(n\log n)$ time.

A polygon C is an intersecting polygon for a set O of objects in the plane if C intersects each object in O, where the polygon includes its interior. We study the problem of computing the minimum-perimeter intersecting polygon and the minimum-area convex intersecting polygon for a given set O of objects. We present an FPTAS for both problems for the case where O is a set of possibly intersecting convex polygons in the plane of total complexity n. Furthermore, we present an exact polynomial-time algorithm for the minimum-perimeter intersecting polygon for the case where O is a set of n possibly intersecting segments in the plane. So far, polynomial-time exact algorithms were only known for the minimum perimeter intersecting polygon of lines or of disjoint segments., Comment: Accepted to ESA 2022

We consider the unlabeled motion-planning problem of $m$ unit-disc robots moving in a simple polygonal workspace of $n$ edges. The goal is to find a motion plan that moves the robots to a given set of $m$ target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time $O(n \log n + mn + m^2)$ if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance $4$ apart, any two target positions are at least distance $4$ apart, and any pair of a start and a target positions is at least distance $3$ apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary., Comment: A shorter version of this paper appeared in the Proceedings of the 38th International Symposium on Computational Geometry (SoCG 2022)

Let $L$ be a set of $n$ axis-parallel lines in $\mathbb{R}^3$. We are are interested in partitions of $\mathbb{R}^3$ by a set $H$ of three planes such that each open cell in the arrangement $\mathcal{A}(H)$ is intersected by as few lines from $L$ as possible. We study such partitions in three settings, depending on the type of splitting planes that we allow. We obtain the following results. $\bullet$ There are sets $L$ of $n$ axis-parallel lines such that, for any set $H$ of three splitting planes, there is an open cell in $\mathcal{A}(H)$ that intersects at least~$\lfloor n/3 \rfloor-1 \approx \frac{1}{3}n$ lines. $\bullet$ If we require the splitting planes to be axis-parallel, then there are sets $L$ of $n$ axis-parallel lines such that, for any set $H$ of three splitting planes, there is an open cell in $\mathcal{A}(H)$ that intersects at least $\frac{3}{2}\lfloor n/4 \rfloor -1 \approx \left( \frac{1}{3}+\frac{1}{24}\right) n$ lines. Furthermore, for any set $L$ of $n$ axis-parallel lines, there exists a set $H$ of three axis-parallel splitting planes such that each open cell in $\mathcal{A}(H)$ intersects at most $\frac{7}{18} n = \left( \frac{1}{3}+\frac{1}{18}\right) n$ lines. $\bullet$ For any set $L$ of $n$ axis-parallel lines, there exists a set $H$ of three axis-parallel and mutually orthogonal splitting planes, such that each open cell in $\mathcal{A}(H)$ intersects at most $\lceil \frac{5}{12} n \rceil \approx \left( \frac{1}{3}+\frac{1}{12}\right) n$ lines., Comment: 21 pages, minor changes, accepted to Computing in Geometry and Topology

We consider the following surveillance problem: Given a set $P$ of $n$ sites in a metric space and a set of $k$ robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency $L$ of a schedule is the maximum latency of any site, where the latency of a site $s$ is the supremum of the lengths of the time intervals between consecutive visits to $s$. When $k=1$ the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into $\ell$ groups, for some~$\ell \leq k$, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a $1+\varepsilon$ factor loss in the approximation factor and an $O\left(\left( k/\varepsilon \right)^k\right)$ factor loss in the runtime, for any $\varepsilon >0$. Our second main result shows that an optimal cyclic solution is a $2(1-1/k)$-approximation of the overall optimal solution. Note that for $k=2$ this implies that an optimal cyclic solution is optimal overall. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a $(2(1-1/k)+\varepsilon)$-approximation of the optimal unrestricted solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting., Comment: This paper is accepted in the 38th International Symposium on Computational Geometry (SoCG 2022)

Let $P$ be a set of points in $\mathbb{R}^d$, where each point $p\in P$ has an associated transmission range $\rho(p)$. The range assignment $\rho$ induces a directed communication graph $\mathcal{G}_{\rho}(P)$ on $P$, which contains an edge $(p,q)$ iff $|pq| \leq \rho(p)$. In the broadcast range-assignment problem, the goal is to assign the ranges such that $\mathcal{G}_{\rho}(P)$ contains an arborescence rooted at a designated node and whose cost $\sum_{p \in P} \rho(p)^2$ is minimized. We study trade-offs between the stability of the solution -- the number of ranges that are modified when a point is inserted into or deleted from $P$ -- and its approximation ratio. We introduce $k$-stable algorithms, which are algorithms that modify the range of at most $k$ points when they update the solution. We also introduce the concept of a stable approximation scheme (SAS). A SAS is an update algorithm that, for any given fixed parameter $\varepsilon>0$, is $k(\epsilon)$-stable and maintains a solution with approximation ratio $1+\varepsilon$, where the stability parameter $k(\varepsilon)$ only depends on $\varepsilon$ and not on the size of $P$. We study such trade-offs in three settings. - In $\mathbb{R}^1$, we present a SAS with $k(\varepsilon)=O(1/\varepsilon)$, which we show is tight in the worst case. We also present a 1-stable $(6+2\sqrt{5})$-approximation algorithm, a $2$-stable 2-approximation algorithm, and a $3$-stable $1.97$-approximation algorithm. - In $\mathbb{S}^1$ (where the underlying space is a circle) we prove that no SAS exists, even though an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in $\mathbb{R}^1$. - In $\mathbb{R}^2$, we also prove that no SAS exists, and we present a $O(1)$-stable $O(1)$-approximation algorithm., Comment: abstract shortened to meet the arxiv requirements

The $k$-center problem for a point set~$P$ asks for a collection of $k$ congruent balls (that is, balls of equal radius) that together cover all the points in $P$ and whose radius is minimized. The $k$-center problem with outliers is defined similarly, except that $z$ of the points in $P$ do need not to be covered, for a given parameter $z$. We study the $k$-center problem with outliers in data streams in the sliding-window model. In this model we are given a possibly infinite stream $P=\langle p_1,p_2,p_3,\ldots\rangle$ of points and a time window of length $W$, and we want to maintain a small sketch of the set $P(t)$ of points currently in the window such that using the sketch we can approximately solve the problem on $P(t)$. We present the first algorithm for the $k$-center problem with outliers in the sliding-window model. The algorithm works for the case where the points come from a space of bounded doubling dimension and it maintains a set $S(t)$ such that an optimal solution on $S(t)$ gives a $(1+\varepsilon)$-approximate solution on $P(t)$. The algorithm is deterministic and uses $O((kz/\varepsilon^d)\log \sigma)$ storage, where $d$ is the doubling dimension of the underlying space and $\sigma$ is the spread of the points in the stream. Algorithms providing a $(1+\varepsilon)$-approximation were not even known in the setting without outliers or in the insertion-only setting with outliers. We also present a lower bound showing that any algorithm that provides a $(1+\varepsilon)$-approximation must use $\Omega((kz/\varepsilon)\log \sigma)$ storage., Comment: appeared in ESA 2021

Let $F$ be a set of $n$ objects in the plane and let $G(F)$ be its intersection graph. A balanced clique-based separator of $G(F)$ is a set $S$ consisting of cliques whose removal partitions $G(F)$ into components of size at most $\delta n$, for some fixed constant $\delta<1$. The weight of a clique-based separator is defined as $\sum_{C\in S}\log (|C|+1)$. Recently De Berg et al. (SICOMP 2020) proved that if $S$ consists of convex fat objects, then $G(F)$ admits a balanced clique-based separator of weight $O(\sqrt{n})$. We extend this result in several directions, obtaining the following results. Map graphs admit a balanced clique-based separator of weight $O(\sqrt{n})$, which is tight in the worst case. Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight $O(n^{2/3}\log n)$. If the pseudo-disks are polygonal and of total complexity $O(n)$ then the weight of the separator improves to $O(\sqrt{n}\log n)$. Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight $O(n^{2/3}\log n)$. Visibility-restricted unit-disk graphs in a polygonal domain with $r$ reflex vertices admit a balanced clique-based separator of weight $O(\sqrt{n}+r\log(n/r))$, which is tight in the worst case. These results immediately imply sub-exponential algorithms for MAXIMUM INDEPENDENT SET (and, hence, VERTEX COVER), for FEEDBACK VERTEX SET, and for $q$-COLORING for constant $q$ in these graph classes., Comment: 23 pages, 8 figures

We present subquadratic algorithms in the algebraic decision-tree model for several \textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Given two sets $A$, $B$, each consisting of $n$ pairwise disjoint segments in the plane, and a set $C$ of $n$ triangles in the plane, we want to count, for each triangle $\Delta\in C$, the number of intersection points between the segments of $A$ and those of $B$ that lie in $\Delta$. The problems considered in this paper have been studied by Chan~(2020), who gave algorithms that solve them, in the standard real-RAM model, in $O((n^2/\log^2n)\log^{O(1)}\log n)$ time. We present solutions in the algebraic decision-tree model whose cost is $O(n^{60/31+\varepsilon})$, for any $\varepsilon>0$. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl~(2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the \emph{order type} of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm., Comment: 28 pages, 1 figure, full version of a paper in ISAAC'21

A rectilinear Steiner tree for a set $P$ of points in $\mathbb{R}^2$ is a tree that connects the points in $P$ using horizontal and vertical line segments. The goal of Minimal Rectilinear Steiner Tree is to find a rectilinear Steiner tree with minimal total length. We investigate how the complexity of Minimal Rectilinear Steiner Tree for point sets $P$ inside the strip $(-\infty,+\infty)\times [0,\delta]$ depends on the strip width $\delta$. We obtain two main results. 1) We present an algorithm with running time $n^{O(\sqrt{\delta})}$ for sparse point sets, that is, point sets where each $1\times\delta$ rectangle inside the strip contains $O(1)$ points. 2) For random point sets, where the points are chosen randomly inside a rectangle of height $\delta$ and expected width $n$, we present an algorithm that is fixed-parameter tractable with respect to $\delta$ and linear in $n$. It has an expected running time of $2^{O(\delta \sqrt{\delta})} n$., Comment: 21 pages, 13 figures

Let $P=\{p_0,\ldots,p_{n-1}\}$ be a set of points in $\mathbb{R}^d$, modeling devices in a wireless network. A range assignment assigns a range $r(p_i)$ to each point $p_i\in P$, thus inducing a directed communication graph $G_r$ in which there is a directed edge $(p_i,p_j)$ iff $\textrm{dist}(p_i, p_j) \leq r(p_i)$, where $\textrm{dist}(p_i,p_j)$ denotes the distance between $p_i$ and $p_j$. The range-assignment problem is to assign the transmission ranges such that $G_r$ has a certain desirable property, while minimizing the cost of the assignment; here the cost is given by $\sum_{p_i\in P} r(p_i)^{\alpha}$, for some constant $\alpha>1$ called the distance-power gradient. We introduce the online version of the range-assignment problem, where the points $p_j$ arrive one by one, and the range assignment has to be updated at each arrival. Following the standard in online algorithms, resources given out cannot be taken away -- in our case this means that the transmission ranges will never decrease. The property we want to maintain is that $G_r$ has a broadcast tree rooted at the first point $p_0$. Our results include the following. - For $d=1$, a 1-competitive algorithm does not exist. In particular, for $\alpha=2$ any online algorithm has competitive ratio at least 1.57. - For $d=1$ and $d=2$, we analyze two natural strategies: Upon the arrival of a new point $p_j$, Nearest-Neighbor increases the range of the nearest point to cover $p_j$ and Cheapest Increase increases the range of the point for which the resulting cost increase to be able to reach $p_j$ is minimal. - We generalize the problem to arbitrary metric spaces, where we present an $O(\log n)$-competitive algorithm., Comment: Preliminary version in ISAAC 2020

We consider the problem of finding patrol schedules for $k$ robots to visit a given set of $n$ sites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling salesman problem as a special case (when $k=1$ and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of $O(k^2 \log \frac{w_{\max}}{w_{\min}})$ to the optimal solution, where $w_{\max}$ and $w_{\min}$ are the maximum and minimum weight of the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. If the sites may have different weights, we present a $12$-approximate solution, which runs in polynomial time when the number of robots, $k$, is a constant., Comment: Proceedings of the 14th International Workshop on the Algorithmic Foundations of Robotics (WAFR 20)

We investigate how the complexity of Euclidean TSP for point sets $P$ inside the strip $(-\infty,+\infty)\times [0,\delta]$ depends on the strip width $\delta$. We obtain two main results. First, for the case where the points have distinct integer $x$-coordinates, we prove that a shortest bitonic tour (which can be computed in $O(n\log^2 n)$ time using an existing algorithm) is guaranteed to be a shortest tour overall when $\delta\leq 2\sqrt{2}$, a bound which is best possible. Second, we present an algorithm that is fixed-parameter tractable with respect to $\delta$. Our algorithm has running time $2^{O(\sqrt{\delta})} n + O(\delta^2 n^2)$ for sparse point sets, where each $1\times\delta$ rectangle inside the strip contains $O(1)$ points. For random point sets, where the points are chosen uniformly at random from the rectangle $[0,n]\times [0,\delta]$, it has an expected running time of $2^{O(\sqrt{\delta})} n$. These results generalise to point sets $P$ inside a hypercylinder of width $\delta$. In this case, the factors $2^{O(\sqrt{\delta})}$ become $2^{O(\delta^{1-1/d})}$., Comment: To appear in Discrete & Computational Geometry. See also earlier version in Proceedings 36th International Symposium on Computational Geometry (SoCG 2020)

Let $V$ be a set of $n$ points in $\mathbb{R}^d$, called voters. A point $p\in \mathbb{R}^d$ is a plurality point for $V$ when the following holds: for every $q\in\mathbb{R}^d$ the number of voters closer to $p$ than to $q$ is at least the number of voters closer to $q$ than to $p$. Thus, in a vote where each $v\in V$ votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal $p$ will not lose against any alternative proposal $q$. For most voter sets a plurality point does not exist. We therefore introduce the concept of $\beta$-plurality points, which are defined similarly to regular plurality points except that the distance of each voter to $p$ (but not to $q$) is scaled by a factor $\beta$, for some constant $0<\beta\leq 1$. We investigate the existence and computation of $\beta$-plurality points, and obtain the following. * Define $\beta^*_d := \sup \{ \beta : \text{any finite multiset $V$ in $\mathbb{R}^d$ admits a $\beta$-plurality point} \}$. We prove that $\beta^*_2 = \sqrt{3}/2$, and that $1/\sqrt{d} \leq \beta^*_d \leq \sqrt{3}/2$ for all $d\geq 3$. * Define $\beta(p, V) := \sup \{ \beta : \text{$p$ is a $\beta$-plurality point for $V$}\}$. Given a voter set $V \in \mathbb{R}^2$, we provide an algorithm that runs in $O(n \log n)$ time and computes a point $p$ such that $\beta(p, V) \geq \beta^*_2$. Moreover, for $d\geq 2$ we can compute a point $p$ with $\beta(p,V) \geq 1/\sqrt{d}$ in $O(n)$ time. * Define $\beta(V) := \sup \{ \beta : \text{$V$ admits a $\beta$-plurality point}\}$. We present an algorithm that, given a voter set $V$ in $\mathbb{R}^d$, computes an $(1-\varepsilon)\cdot \beta(V)$ plurality point in time $O(\frac{n^2}{\varepsilon^{3d-2}} \cdot \log \frac{n}{\varepsilon^{d-1}} \cdot \log^2 \frac {1}{\varepsilon})$., Comment: 21 pages, 10 figures, SoCG'20

Let $V$ be a multiset of $n$ points in $\mathbb{R}^d$, which we call voters, and let $k\geq 1$ and $\ell\geq 1$ be two given constants. We consider the following game, where two players $\mathcal{P}$ and $\mathcal{Q}$ compete over the voters in $V$: First, player $\mathcal{P}$ selects $k$ points in $\mathbb{R}^d$, and then player $\mathcal{Q}$ selects $\ell$ points in $\mathbb{R}^d$. Player $\mathcal{P}$ wins a voter $v\in V$ iff $\mathrm{dist}(v,P) \leq \mathrm{dist}(v,Q)$, where $\mathrm{dist}(v,P) := \min_{p\in P} \mathrm{dist}(v,p)$ and $\mathrm{dist}(v,Q)$ is defined similarly. Player $\mathcal{P}$ wins the game if he wins at least half the voters. The algorithmic problem we study is the following: given $V$, $k$, and $\ell$, how efficiently can we decide if player $\mathcal{P}$ has a winning strategy, that is, if $\mathcal{P}$ can select his $k$ points such that he wins the game no matter where $\mathcal{Q}$ places her points. Banik et al. devised a singly-exponential algorithm for the game in $\mathbb{R}^1$, for the case $k=\ell$. We improve their result by presenting the first polynomial-time algorithm for the game in $\mathbb{R}^1$. Our algorithm can handle arbitrary values of $k$ and $\ell$. We also show that if $d\geq 2$, deciding if player $\mathcal{P}$ has a winning strategy is $\Sigma_2^P$-hard when $k$ and $\ell$ are part of the input. Finally, we prove that for any dimension $d$, the problem is contained in the complexity class $\exists\forall \mathbb{R}$, and we give an algorithm that works in polynomial time for fixed $k$ and $\ell$., Comment: 25 pages

We study exact algorithms for Euclidean TSP in $\mathbb{R}^d$. In the early 1990s algorithms with $n^{O(\sqrt{n})}$ running time were presented for the planar case, and some years later an algorithm with $n^{O(n^{1-1/d})}$ running time was presented for any $d\geq 2$. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no $2^{O(n^{1-1/d-\epsilon})}$ algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a $2^{O(n^{1-1/d})}$ algorithm and by showing that a $2^{o(n^{1-1/d})}$ algorithm does not exist unless ETH fails., Comment: FOCS 2018, to appear in SICOMP

It is well known that any set of n intervals in $\mathbb{R}^1$ 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.

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 intersection graphs 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 are representation-agnostic, i.e., they work on the graph itself and do not require the geometric representation. 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., Comment: 41 pages. v4 corrects a small mistake in the conference version of Theorem 1 by slightly restricting its scope and adding Lemma 4 to its proof

We study dynamic conflict-free colorings in the plane, where the goal is to maintain a conflict-free coloring (CF-coloring for short) under insertions and deletions. - First we consider CF-colorings of a set $S$ of unit squares with respect to points. Our method maintains a CF-coloring that uses $O(\log n)$ colors at any time, where $n$ is the current number of squares in $S$, at the cost of only $O(\log n)$ recolorings per insertion or deletion of a square. We generalize the method to rectangles whose sides have lengths in the range $[1,c]$, where $c$ is a fixed constant. Here the number of used colors becomes $O(\log^2 n)$. The method also extends to arbitrary rectangles whose coordinates come from a fixed universe of size $N$, yielding $O(\log^2 N \log^2 n)$ colors. The number of recolorings for both methods stays in $O(\log n)$. - We then present a general framework to maintain a CF-coloring under insertions for sets of objects that admit a unimax coloring with a small number of colors in the static case. As an application we show how to maintain a CF-coloring with $O(\log^3 n)$ colors for disks (or other objects with linear union complexity) with respect to points at the cost of $O(\log n)$ recolorings per insertion. We extend the framework to the fully-dynamic case when the static unimax coloring admits weak deletions. As an application we show how to maintain a CF-coloring with $O(\sqrt{n} \log^2 n)$ colors for points with respect to rectangles, at the cost of $O(\log n)$ recolorings per insertion and $O(1)$ recolorings per deletion. These are the first results on fully-dynamic CF-colorings in the plane, and the first results for semi-dynamic CF-colorings for non-congruent objects.

We study the parameterized complexity of dominating sets in geometric intersection graphs. In one dimension, we investigate intersection graphs induced by translates of a fixed pattern Q that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever Q contains at least one interval, and whenever Q contains no intervals and for any two point pairs in Q the distance ratio is rational. The remaining case where Q contains no intervals but does contain an irrational distance ratio is shown to be NP-complete and contained in FPT (when parameterized by the solution size). In two and higher dimensions, we prove that Dominating Set is contained in W[1] for intersection graphs of semi-algebraic sets with constant description complexity. This generalizes known results from the literature. Finally, we establish W[1]-hardness for a large class of intersection graphs., Comment: 19 pages. Preliminary version appears in the proceedings of IPEC 2017

In a geometric $k$-clustering problem the goal is to partition a set of points in $\mathbb{R}^d$ into $k$ subsets such that a certain cost function of the clustering is minimized. We present data structures for orthogonal range-clustering queries on a point set $S$: given a query box $Q$ and an integer $k>2$, compute an optimal $k$-clustering for $S\setminus Q$. We obtain the following results. We present a general method to compute a $(1+\epsilon)$-approximation to a range-clustering query, where $\epsilon>0$ is a parameter that can be specified as part of the query. Our method applies to a large class of clustering problems, including $k$-center clustering in any $L_p$-metric and a variant of $k$-center clustering where the goal is to minimize the sum (instead of maximum) of the cluster sizes. We extend our method to deal with capacitated $k$-clustering problems, where each of the clusters should not contain more than a given number of points. For the special cases of rectilinear $k$-center clustering in $\mathbb{R}^1$, and in $\mathbb{R}^2$ for $k=2$ or 3, we present data structures that answer range-clustering queries exactly., Comment: 23 pages and 2 figures

Let $P$ be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let $s\in P$ be a given source node. Each node $p$ can transmit information to all other nodes within unit distance, provided $p$ is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source $s$ can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem (in the latter, $s$ must be able to reach every node within a specified number of hops), with the restriction that all points lie inside a strip of width $w$. We almost completely characterize the complexity of both the regular and the hop-bounded versions as a function of the strip width $w$., Comment: 50 pages, WADS 2017 submission

Let $P$ be a set of $n$ points in the plane. We consider the problem of partitioning $P$ into two subsets $P_1$ and $P_2$ such that the sum of the perimeters of $\text{CH}(P_1)$ and $\text{CH}(P_2)$ is minimized, where $\text{CH}(P_i)$ denotes the convex hull of $P_i$. The problem was first studied by Mitchell and Wynters in 1991 who gave an $O(n^2)$ time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in $O(n \log^2 n)$ time and a $(1+\varepsilon)$-approximation algorithm running in $O(n + 1/\varepsilon^2\cdot\log^2(1/\varepsilon))$ time., Comment: This version is similar to one published in Discrete & Computational Geometry

We present a new algorithm for the widely used density-based clustering method DBscan. Our algorithm computes the DBscan-clustering in $O(n\log n)$ time in $\mathbb{R}^2$, irrespective of the scale parameter $\varepsilon$ (and assuming the second parameter MinPts is set to a fixed constant, as is the case in practice). Experiments show that the new algorithm is not only fast in theory, but that a slightly simplified version is competitive in practice and much less sensitive to the choice of $\varepsilon$ than the original DBscan algorithm. We also present an $O(n\log n)$ randomized algorithm for HDBscan in the plane---HDBscan is a hierarchical version of DBscan introduced recently---and we show how to compute an approximate version of HDBscan in near-linear time in any fixed dimension.

We introduce the fully-dynamic conflict-free coloring problem for a set $S$ of intervals in $\mathbb{R}^1$ with respect to points, where the goal is to maintain a conflict-free coloring for$S$ under insertions and deletions. A coloring is conflict-free if for each point $p$ contained in some interval, $p$ is contained in an interval whose color is not shared with any other interval containing $p$. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include: - a lower bound on the number of recolorings as a function of the number of colors, which implies that with $O(1)$ recolorings per update the worst-case number of colors is $\Omega(\log n/\log\log n)$, and that any strategy using $O(1/\varepsilon)$ colors needs $\Omega(\varepsilon n^{\varepsilon})$ recolorings; - a coloring strategy that uses $O(\log n)$ colors at the cost of $O(\log n)$ recolorings, and another strategy that uses $O(1/\varepsilon)$ colors at the cost of $O(n^{\varepsilon}/\varepsilon)$ recolorings; - stronger upper and lower bounds for special cases. We also consider the kinetic setting where the intervals move continuously (but there are no insertions or deletions); here we show how to maintain a coloring with only four colors at the cost of three recolorings per event and show this is tight., Comment: 18 pages, 8 figures

More than 25 years ago Chazelle~\emph{et al.} (FOCS 1991) studied the following question: Is it possible to cut any set of $n$ lines in ${\Bbb R}^3$ into a subquadratic number of fragments such that the resulting fragments admit a depth order? They proved an $O(n^{9/4})$ bound for the very special case of bipartite weavings of lines. Since then only little progress was made, until a recent breakthrough by Aronov and Sharir (STOC 2016) who showed that $O(n^{3/2}\mathrm{polylog}\; n)$ fragments suffice for any set of lines. In a follow-up paper Aronov, Miller and Sharir (SODA 2017) proved an $O(n^{3/2+\varepsilon})$ bound for triangles, but their method results in pieces with curved boundaries. Moreover, their method uses polynomial partitions, for which currently no algorithm is known. Thus the most natural version of the problem is still wide open: Can we cut any collection of $n$ disjoint triangles in ${\Bbb R}^3$ into a subquadratic number of triangular fragments that admit a depth order? And if so, can we compute the cuts efficiently? We answer this question by presenting an algorithm that cuts any set of $n$ disjoint triangles in ${\Bbb R}^3$ into $O(n^{7/4}\mathrm{polylog}\; n)$ triangular fragments that admit a depth order. The running time of our algorithm is $O(n^{3.69})$. We also prove a refined bound that depends on the number, $K$, of intersections between the projections of the triangle edges onto the $xy$-plane: we show that $O(n^{1+\varepsilon} + n^{1/4} K^{3/4}\mathrm{polylog}\; n)$ fragments suffice to obtain a depth order. This result extends to $xy$-monotone surface patches bounded by a constant number of bounded-degree algebraic arcs, constituting the first subquadratic bound for surface patches. As a byproduct of our approach we obtain a faster algorithm to cut a set of lines into $O(n^{3/2}\mathrm{polylog}\; n)$ fragments that admit a depth order., Comment: Updated version (18 pages, 3 figures). This updated version has a more extensive abstract and introduction, has intuitive explanations and details added at various points, and has a runtime analysis for the case of surface patches

Let $C$ be the unit circle in $\mathbb{R}^2$. We can view $C$ as a plane graph whose vertices are all the points on $C$, and the distance between any two points on $C$ is the length of the smaller arc between them. We consider a graph augmentation problem on $C$, where we want to place $k\geq 1$ \emph{shortcuts} on $C$ such that the diameter of the resulting graph is minimized. We analyze for each $k$ with $1\leq k\leq 7$ what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of~$k$. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is $2 + \Theta(1/k^{\frac{2}{3}})$ for any~$k$., Comment: An extended abstract appeared in ISAAC 2017