Recently, motivated by the rapid increase of the data size in various applications, Monemizadeh [APPROX'23] and Driemel, Monemizadeh, Oh, Staals, and Woodruff [SoCG'25] studied geometric problems in the setting where the only access to the input point set is via querying a range-search oracle. Algorithms in this setting are evaluated on two criteria: (i) the number of queries to the oracle and (ii) the error of the output. In this paper, we continue this line of research and investigate one of the most fundamental geometric problems in the oracle setting, i.e., the convex hull problem. Let P be an unknown set of points in [0,1]^d equipped with a range-emptiness oracle. Via querying the oracle, the algorithm is supposed to output a convex polygon C ⊆ [0,1]^d as an estimation of the convex hull CH(P) of P. The error of the output is defined as the volume of the symmetric difference C ⊕ CH(P) = (C∖CH(P)) ∪ (CH(P)∖C). We prove tight and near-tight tradeoffs between the number of queries and the error of the output for different variants of the problem, depending on the type of the range-emptiness queries and whether the queries are non-adaptive or adaptive. - Orthogonal emptiness queries in d-dimensional space: We show that the minimum error a deterministic algorithm can achieve with q queries is Θ(q^{-1/d}) if the queries are non-adaptive, and Θ(q^{-1/(d-1)}) if the queries are adaptive. In particular, in 2D, the bounds are Θ(1/√q) and Θ(1/q) for non-adaptive and adaptive queries, respectively. - Halfplane emptiness queries in 2D: We show that the minimum error a deterministic algorithm can achieve with q queries is Θ(1/√q) if the queries are non-adaptive, and Θ̃(1/q²) if the queries are adaptive. Here Θ̃(⋅) hides logarithmic factors.

In the Rectangle Stabbing problem, input is a set R of axis-parallel rectangles and a set L of axis-parallel lines in the plane. The task is to find a minimum size set L^* ⊆ L such that for every rectangle R ∈ R there is a line 𝓁 ∈ L^* such that 𝓁 intersects R. Gaur et al. [Journal of Algorithms, 2002] gave a polynomial time 2-approximation algorithm, while Dom et al. [WALCOM 2009] and Giannopoulos et al. [EuroCG 2009] independently showed that, assuming FPT ≠ W[1], there is no algorithm with running time f(k)(|L||R|)^O(1) that determines whether there exists an optimal solution with at most k lines. We give the first parameterized approximation algorithm for the problem with a ratio better than 2. In particular we give an algorithm that given R, L, and an integer k runs in time k^O(k)(|L||R|)^O(1) and either correctly concludes that there does not exist a solution with at most k lines, or produces a solution with at most 7k/4 lines. We complement our algorithm by showing that unless FPT = W[1], the Rectangle Stabbing problem does not admit a (5/4-ε)-approximation algorithm running in f(k)(|L||R|)^O(1) time for any function f and ε > 0.

Given a simple polygon P with n vertices, we consider the problem of constructing a data structure for visibility queries: for any query point q ∈ P, compute the visibility polygon of q in P. To obtain O(log n + k) query time, where k is the size of the visibility polygon of q, the previous best result requires O(n³) space. In this paper, we propose a new data structure that uses O(n^{2+ε}) space, for any ε > 0, while achieving the same query time. If only O(n²) space is available, the best known result provides O(log² n + k) query time. We improve this to O(log n log log n + k) time. When restricted to o(n²) space, the only previously known approach, aside from the O(n)-time algorithm that computes the visibility polygon without preprocessing, is an O(n)-space data structure that supports O(k log n)-time queries. We construct a data structure using O(n log n) space that answers visibility queries in O(n^{1/2+ε} + k) time. In addition, for the special case in which q lies on the boundary of P, we build a data structure of O(n log n) space supporting O(log² n + k) query time; alternatively, we achieve O(log n + k) query time using O(n^{1+ε}) space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.

We study two fundamental geometric problems on a dynamic set of n axis-parallel boxes in d-dimensional space. The maximum depth problem asks for the largest number of boxes that contain a common point, whereas Klee’s measure problem asks for the volume of the union of the boxes. We present fully dynamic exact data structures for both problems achieving Õ(n^{(d-1)/2}) amortized update time. This update time is optimal for an exact dynamic algorithm, up to logarithmic factors, assuming the Combinatorial k-Clique Hypothesis. Previously, matching bounds were established only for d = 1 [Imai and Asano, J. Algo.'83], and for d = 2 [Suri, Xue, Yang, and Zhu, SoCG'25]. Our approach integrates a classic grid-based partition framework with a novel charging analysis that controls the cost of structure-sensitive offline routines within each cell. This argument allows us to perform a global aggregation of the update time, by circumventing the worst-case costs associated with individual cell updates. We believe this technique may be of independent interest for other dynamic geometric problems.

Courcelle’s theorem states that there exists an algorithm that takes as input a graph G of treewidth at most t and a MSO formula φ, and determines whether G satisfies φ in time f(φ,t) · n. It is folklore that the function f contains a tower of exponentials whose height depends as a linear function of the number of quantifier alternations of the input formula φ. A classic reduction of Frick and Grohe shows that, assuming the Exponential Time Hypothesis (ETH), the linear growth of the height of the tower is unavoidable. Nevertheless, there is still a huge gap between existing upper and lower bounds – after all, there is quite a difference between a single exponential and a double exponential running time. In addition, this only gives us a very coarse understanding in the time complexity of Courcelle’s theorem. In this paper, we prove a fine-grained version of Courcelle’s theorem with nearly ETH-tight dependence on the treewidth parameter t and the quantifier structure of φ (specifically, the number of first order and second order variables in each quantifier alternation block).

In this paper, we present efficient algorithms for the single-source shortest path problem in weighted disk graphs. A disk graph is the intersection graph of a family of disks in the plane. Here, the weight of an edge is defined as the Euclidean distance between the centers of the disks corresponding to the endpoints of the edge. Given a family of $n$ disks in the plane whose radii lie in $[1,Ψ]$ and a source disk, we can compute a shortest path tree from a source vertex in the weighted disk graph in $O(n\log^2 n \log Ψ)$ time. Moreover, in the case that the radii of disks are arbitrarily large, we can compute a shortest path tree from a source vertex in the weighted disk graph in $O(n\log^4 n)$ time. This improves the best-known algorithm running in $O(n\log^6 n)$ time presented in ESA'23.

Let G = (V,E) be a directed graph on n vertices where each vertex has out-degree k. We say that G is kNN-realizable in d-dimensional Euclidean space if there exists a point set P = {p_1, p_2, …, p_n} in ℝ^d along with a one-to-one mapping ϕ: V → P such that for any u,v ∈ V, u is an out-neighbor of v in G if and only if ϕ(u) is one of the k nearest neighbors of ϕ(v); we call the map ϕ a kNN-realization of G in ℝ^d. The kNN-realization problem, which aims to compute a kNN-realization of an input graph in ℝ^d, is known to be NP-hard already for d = 2 and k = 1 [Eades and Whitesides, Theoretical Computer Science, 1996], and to the best of our knowledge has not been studied in dimension d = 1. The main results of this paper are the following: - For any fixed dimension d ≥ 2, we can efficiently compute an embedding realizing at least a 1 - ε fraction of G’s edges, or conclude that G is not kNN-realizable in ℝ^d. - For d = 1, we can decide in O(kn) time whether G is kNN-realizable and, if so, compute a realization in O(n^{2.5} poly(log n)) time.

We prove a robust contraction decomposition theorem for $H$-minor-free graphs, which states that given an $H$-minor-free graph $G$ and an integer $p$, one can partition in polynomial time the vertices of $G$ into $p$ sets $Z_1,\dots,Z_p$ such that $\operatorname{tw}(G/(Z_i \setminus Z')) = O(p + |Z'|)$ for all $i \in [p]$ and $Z' \subseteq Z_i$. Here, $\operatorname{tw}(\cdot)$ denotes the treewidth of a graph and $G/(Z_i \setminus Z')$ denotes the graph obtained from $G$ by contracting all edges with both endpoints in $Z_i \setminus Z'$. Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et al. [STOC 2011] based on partitioning $E(G)$, and some recent theorems for planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022]. The robust contraction decomposition theorem directly results in parameterized algorithms with running time $2^{\widetilde{O}(\sqrt{k})} \cdot n^{O(1)}$ or $n^{O(\sqrt{k})}$ for every vertex/edge deletion problems on $H$-minor-free graphs that can be formulated as Permutation CSP Deletion or 2-Conn Permutation CSP Deletion. Consequently, we obtain the first subexponential-time parameterized algorithms for Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn Component Order Connectivity on $H$-minor-free graphs. For other problems which already have subexponential-time parameterized algorithms on $H$-minor-free graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut, etc.), our theorem gives much simpler algorithms of the same running time.

The Euclidean Traveling Salesman Problem with Neighborhoods (ETSPN) is a well-studied problem in computational geometry and has a wealth of results. In this problem, given a set of geometric neighborhoods (or regions), the goal is to compute a shortest route that visits at least one point of each neighborhood. The problem is a generalization of the standard Euclidean TSP and hence is also NP-hard, even when the neighborhoods are disjoint unit disks or unit squares in the plane. A longstanding open problem on this topic is the existence of PTASes for ETSPN with unit disk (and unit square) neighborhoods. Prior to this work, the best-known approximation factor for unit disks is 6.75, and PTASes are only known for the special case where the unit disks/squares are of bounded depth, i.e., each point lies in at most a constant number of disks.

A drawing of an (undirected) graph G is a mapping φ that assigns to each vertex a distinct point in the plane and to each edge uw a continuous curve φ (uυ ) in the plane from φ (η ) to φ(ν ), not passing through the image of any other vertex. Two edges e and f cross in a point p if p € φ (e ) ∩ φ (f ) and p is not the image of a vertex of G. In a drawing no three edges are allowed to cross in the same point. The crossing number of a drawing of G is the number of points p such that some two edges e and f cross in p. In the CROSSING Number problem, the input consists of a graph G and integer k. The task is to determine whether there exists a drawing of G with crossing number at most k, and to output such a drawing if it exists.

In the CAPACITATED d-HlTTING Set problem input is a universe U equipped with a capacity function cap : U → ℕ, and a collection A of subsets of U, each of size at most d. The task is to find a minimum size subset S of U and an assignment φ : A → S such that, for every set A ∈ A we have φ (Α ) ∈ A and for every x ∈ U we have |φ-1(χ)| ≤ cap(x ). Here φ-1(χ) is the collection of sets in A mapped to x by φ. Such a set S is called a capacitated hitting set. When d = 2 the problem is known under the name CAPACITATED VERTEX COVER. In Weighted Capacitated d-HlTTING Set each element of U has a positive integer weight and the goal is to find a capacitated hitting set of minimum weight.

Abstract. Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirements) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in one and two dimensions, which significantly improve and extend the previous results. Our results include the following: (1) The first data structure for [Formula: see text]-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of [Formula: see text], improving the [Formula: see text] bound of Agarwal et al. [ Proceedings of the 36 th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020, 27; ACM Trans. Algorithms, 18 (2022), 40], where [Formula: see text] denotes an arbitrarily small constant. (2) A data structure for [Formula: see text]-approximate dynamic unit-square set cover with [Formula: see text] amortized update time, substantially improving the [Formula: see text] update time of Agarwal et al. (3) A data structure for [Formula: see text]-approximate dynamic square set cover with [Formula: see text] randomized amortized update time, improving the [Formula: see text] update time of Chan and He [ Proceedings of the 36 th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020; J. Comput. Geom., 13 (2022), pp. 90–114]. (4) A data structure for [Formula: see text]-approximate dynamic two-dimensional half-plane set cover with [Formula: see text] randomized amortized update time. The previous solution for a half-plane set cover by Chan and He [ Proceedings of the 37 th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 189, Schloss Dagstuhl - Leibniz Center for Informatics, 2021, 25; J. Comput. Geom., 13 (2022), pp. 90–114] is slower and can only report the size of the approximate solution. (5) The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for [Formula: see text]-approximate dynamic weighted interval set cover with [Formula: see text] amortized update time and a data structure for [Formula: see text]-approximate dynamic weighted unit-square set cover with [Formula: see text] amortized update time.

In a disk graph, every vertex corresponds to a disk in $\mathbb{R}^2$ and two vertices are connected by an edge whenever the two corresponding disks intersect. Disk graphs form an important class of geometric intersection graphs, which generalizes both planar graphs and unit-disk graphs. We study a fundamental optimization problem in algorithmic graph theory, Bipartization (also known as Odd Cycle Transversal), on the class of disk graphs. The goal of Bipartization is to delete a minimum number of vertices from the input graph such that the resulting graph is bipartite. A folklore (polynomial-time) $3$-approximation algorithm for Bipartization on disk graphs follows from the classical framework of Goemans and Williamson [Combinatorica'98] for cycle-hitting problems. For over two decades, this result has remained the best known approximation for the problem (in fact, even for Bipartization on unit-disk graphs). In this paper, we achieve the first improvement upon this result, by giving a $(3-α)$-approximation algorithm for Bipartization on disk graphs, for some constant $α>0$. Our algorithm directly generalizes to the broader class of pseudo-disk graphs. Furthermore, our algorithm is robust in the sense that it does not require a geometric realization of the input graph to be given.

Given in the plane a set of points and a set of halfplanes, we consider the problem of computing a smallest subset of halfplanes whose union covers all points. In this paper, we present an $O(n^{4/3}\log^{5/3}n\log^{O(1)}\log n)$-time algorithm for the problem, where $n$ is the total number of all points and halfplanes. This improves the previously best algorithm of $n^{10/3}2^{O(\log^*n)}$ time by roughly a quadratic factor. For the special case where all halfplanes are lower ones, our algorithm runs in $O(n\log n)$ time, which improves the previously best algorithm of $n^{4/3}2^{O(\log^*n)}$ time and matches an $Ω(n\log n)$ lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in $O(n\log n)$ time, which in turn leads to an $O(n\log n)$-time algorithm for computing an instance-optimal $ε$-kernel of a set of $n$ points in the plane. Agarwal and Har-Peled presented an $O(nk\log n)$-time algorithm for this problem in SoCG 2023, where $k$ is the size of the $ε$-kernel; they also raised an open question whether the problem can be solved in $O(n\log n)$ time. Our result thus answers the open question affirmatively.

Geometric matching is an important topic in computational geometry and has been extensively studied over decades. In this paper, we study a geometric-matching problem, known as geometric many-to-many matching. In this problem, the input is a set S of n colored points in ℝ^d, which implicitly defines a graph G = (S,E(S)) where E(S) = {(p,q): p,q ∈ S have different colors}, and the goal is to compute a minimum-cost subset E^* ⊆ E(S) of edges that cover all points in S. Here the cost of E^* is the sum of the costs of all edges in E^*, where the cost of a single edge e is the Euclidean distance (or more generally, the L_p-distance) between the two endpoints of e. Our main result is a (1+ε)-approximation algorithm with an optimal running time O_ε(n log n) for geometric many-to-many matching in any fixed dimension, which works under any L_p-norm. This is the first near-linear approximation scheme for the problem in any d ≥ 2. Prior to this work, only the bipartite case of geometric many-to-many matching was considered in ℝ¹ and ℝ², and the best known approximation scheme in ℝ² takes O_ε(n^{1.5} ⋅ poly(log n)) time.

Let $X$ be a set of points in $\mathbb{R}^2$ and $\mathcal{O}$ be a set of geometric objects in $\mathbb{R}^2$, where $|X| + |\mathcal{O}| = n$. We study the problem of computing a minimum subset $\mathcal{O}^* \subseteq \mathcal{O}$ that encloses all points in $X$. Here a point $x \in X$ is enclosed by $\mathcal{O}^*$ if it lies in a bounded connected component of $\mathbb{R}^2 \backslash (\bigcup_{O \in \mathcal{O}^*} O)$. We propose two algorithmic frameworks to design polynomial-time approximation algorithms for the problem. The first framework is based on sparsification and min-cut, which results in $O(1)$-approximation algorithms for unit disks, unit squares, etc. The second framework is based on LP rounding, which results in an $O(α(n)\log n)$-approximation algorithm for segments, where $α(n)$ is the inverse Ackermann function, and an $O(\log n)$-approximation algorithm for disks.

We study a fundamental problem in Computational Geometry, the planar two-center problem. In this problem, the input is a set $S$ of $n$ points in the plane and the goal is to find two smallest congruent disks whose union contains all points of $S$. A longstanding open problem has been to obtain an $O(n\log n)$-time algorithm for planar two-center, matching the $Ω(n\log n)$ lower bound given by Eppstein [SODA'97]. Towards this, researchers have made a lot of efforts over decades. The previous best algorithm, given by Wang [SoCG'20], solves the problem in $O(n\log^2 n)$ time. In this paper, we present an $O(n\log n)$-time (deterministic) algorithm for planar two-center, which completely resolves this open problem.

$\newcommand{\eps}{\varepsilon}$ We observe that a $(1-\eps)$-approximation algorithm to Independent Set, that works for any induced subgraph of the input graph, can be used, via a polynomial time reduction, to provide a $(1+\eps)$-approximation to Vertex Cover. This basic observation was made before, see [BHR11]. As a consequence, we get a PTAS for VC for unweighted pseudo-disks, QQPTAS for VC for unweighted axis-aligned rectangles in the plane, and QPTAS for MWVC for weighted polygons in the plane. To the best of our knowledge all these results are new.

An outerstring graph is the intersection graph of curves lying inside a disk with one endpoint on the boundary of the disk. We show that an outerstring graph with $n$ vertices has treewidth $O(α\log n)$, where $α$ denotes the arboricity of the graph, with an almost matching lower bound of $Ω(α\log (n/α))$. As a corollary, we show that a $t$-biclique-free outerstring graph has treewidth $O(t(\log t)\log n)$. This leads to polynomial-time algorithms for most of the central NP-complete problems such as \textsc{Independent Set}, \textsc{Vertex Cover}, \textsc{Dominating Set}, \textsc{Feedback Vertex Set}, \textsc{Coloring} for sparse outerstring graphs. Also, we can obtain subexponential-time (exact, parameterized, and approximation) algorithms for various NP-complete problems such as \textsc{Vertex Cover}, \textsc{Feedback Vertex Set} and \textsc{Cycle Packing} for (not necessarily sparse) outerstring graphs.

We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input n-vertex m-edge hypergraph$H$of fractional hypertree width at most$\omega$, runs in polynomial time and produces a tree decomposition of$H$of fractional hypertree width$\mathcal{O}(\omega\log n\log\omega)$, i.e., it is an$\mathcal{O}(\log n\log\omega)$-approximation algorithm. As an immediate corollary this yields poly-nomial time$\mathcal{O}(\log^{2}n\log\omega)$-approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial-time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when$\omega$is considered a constant. For hypergraphs where every pair of hyperedges have at most$\eta$vertices in common, the al-gorithm outputs a hypertree decomposition with fractional hypertree width$\mathcal{O}(\eta\omega^{2}\log\omega)$and generalized hypertree width$\mathcal{O}(\eta\omega^{2}\log\omega(\log\eta+\text{log}\omega))$. This ratio is comparable with the recent algorithm of Lanzinger and Razgon [STACS 2024], which produces a hypertree decomposition with generalized hypertree width${\mathcal{O}}(\omega^{2}(\omega+\eta))$, but uses time (at least) exponential in$\eta$and$\omega$. The second algorithm runs in time$n^{\omega}m^{\mathcal{O}(1)}$and pro-duces a tree decomposition of$H$of fractional hypertree width$\mathcal{O}(\omega{\mathrm{l}}\text{og}^{2}\omega)$. This significantly improves over the$(n+m)^{\mathcal{O}(\omega^{3})}$time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hyper-tree width$\mathcal{O}(\omega^{3})$, both in terms of running time and the approximation ratio. Our main technical contribution, and the key insight behind both algorithms, is a variant of the classic Menger's Theorem for clique separators in graphs: For every graph$G$, vertex sets$A$and$B$, family$\mathcal{F}$of cliques in$G$, and positive rational$f$, either there exists a sub-family of$\mathcal{O}(f \cdot {\mathrm{l}}\text{og}^{2}n)$cliques in$\mathcal{F}$whose union separates$A$from$B$, or there exist$f\cdot\log\vert \mathcal{F}\vert$paths from$A$to$B$such that no clique in$\mathcal{F}$intersects more than$\log\vert \mathcal{F}\vert$paths.

In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of n points in ℝ2 called terminals and a parameter k, and the goal is to compute a Steiner tree that spans all the terminals and contains at most k points of ℝ2 as Steiner points such that the maximum edge-length of the Steiner tree is minimized, where the length of a tree edge is the Euclidean distance between its two endpoints. The problem is well-studied and is known to be NP-hard. In this paper, we give a kO(k)nO(1)-time algorithm for Euclidean Bottleneck Steiner Tree, which implies that the problem is fixed-parameter tractable (FPT). This settles an open question explicitly asked by Bae et al. [Algorithmica, 2011], who showed that the ℓ1 and ℓ∞ variants of the problem are FPT. Our approach can be generalized to the problem with ℓp metric for any rational 1 ≤ ρ ≤ ∞, or even other metrics on ℝ2.

We prove a structural theorem for unit-disk graphs, which (roughly) states that given a set \(\mathcal{D}\) of \(n\) unit disks inducing a unit-disk graph \(G_{\mathcal{D}}\) and a number \(p\in[n]\) , one can partition \(\mathcal{D}\) into \(p\) subsets \(\mathcal{D}_{1},\dots,\mathcal{D}_{p}\) such that for every \(i\in[p]\) and every \(\mathcal{D}^{\prime}\subseteq\mathcal{D}_{i}\) , the graph obtained from \(G_{\mathcal{D}}\) by contracting all edges between the vertices in \(\mathcal{D}_{i}\backslash\mathcal{D}^{\prime}\) admits a tree decomposition in which each bag consists of \(O(p+|\mathcal{D}^{\prime}|)\) cliques. Our theorem can be viewed as an analog for unit-disk graphs of the structural theorems for planar graphs and almost-embeddable graphs proved recently by Marx et al. [SODA ’22] and Bandyapadhyay et al. [SODA ’22]. By applying our structural theorem, we give several new combinatorial and algorithmic results for unit-disk graphs. On the combinatorial side, we obtain the first Contraction Decomposition Theorem for unit-disk graphs, resolving an open question in the work by Panolan et al. [SODA ’19]. On the algorithmic side, we obtain a new algorithm for bipartization (also known as odd cycle transversal) on unit-disk graphs, which runs in \(2^{O(\sqrt{k}\log k)}\cdot n^{O(1)}\) time, where \(k\) denotes the solution size. Our algorithm significantly improves the previous slightly subexponential-time algorithm given by Lokshtanov et al. [SODA ’22] which runs in \(2^{O(k^{27/28})}\cdot n^{O(1)}\) time. We also show that the problem cannot be solved in \(2^{o(\sqrt{k})}\cdot n^{O(1)}\) time assuming the Exponential Time Hypothesis, which implies that our algorithm is almost optimal.

Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set X of n points and two numbers k and m, the clustering with outliers aims to exclude m points from X, and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m (i.e., an algorithm with running time of the form f(k, m) * poly(n) for some function f), that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-Median and k-Means with outliers in general and Euclidean metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.

We revisit a natural variant of geometric set cover, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set $S$ of points and a set $\mathcal{R}$ of geometric objects, and the goal is to find a subset $\mathcal{R}^*\subseteq\mathcal{R}$ to cover all points in $S$ such that the \textit{membership} of $S$ with respect to $\mathcal{R}^*$, denoted by $\mathsf{memb}(S,\mathcal{R}^*)$, is minimized, where $\mathsf{memb}(S,\mathcal{R}^*)=\max_{p\in S}|\{R\in\mathcal{R}^*: p\in R\}|$. We achieve the following two main results. * We give the first polynomial-time constant-approximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constant-approximation algorithm with running time $n^{O(\mathsf{opt})}$ where $\mathsf{opt}$ is the optimum of the problem (i.e., the minimum membership). * We give the first polynomial-time approximation scheme (PTAS) for MMGSC with halfplanes. Prior to this work, it was even unknown whether the problem can be approximated with a factor of $o(\log n)$ in polynomial time, while it is well-known that the minimum-size set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimum-ply geometric set cover (MPGSC), in which the goal is to find $\mathcal{R}^*\subseteq\mathcal{R}$ to cover $S$ such that the ply of $\mathcal{R}^*$ is minimized, where the ply is defined as the maximum number of objects in $\mathcal{R}^*$ which have a nonempty common intersection. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in $O(n^{12})$ time. We give a significantly simpler constant-approximation algorithm with near-linear running time.

In the committee selection problem, the goal is to choose a subset of size $k$ from a set of candidates $C$ that collectively gives the best representation to a set of voters. We consider this problem in Euclidean $d$-space where each voter/candidate is a point and voters' preferences are implicitly represented by Euclidean distances to candidates. We explore fault-tolerance in committee selection and study the following three variants: (1) given a committee and a set of $f$ failing candidates, find their optimal replacement; (2) compute the worst-case replacement score for a given committee under failure of $f$ candidates; and (3) design a committee with the best replacement score under worst-case failures. The score of a committee is determined using the well-known (min-max) Chamberlin-Courant rule: minimize the maximum distance between any voter and its closest candidate in the committee. Our main results include the following: (1) in one dimension, all three problems can be solved in polynomial time; (2) in dimension $d \geq 2$, all three problems are NP-hard; and (3) all three problems admit a constant-factor approximation in any fixed dimension, and the optimal committee problem has an FPT bicriterion approximation.

We initiate a systematic study of approximation schemes for fundamental optimization problems on disk graphs, a common generalization of both planar graphs and unit-disk graphs. Our main contribution is a general framework for designing efficient polynomial-time approximation schemes (EPTASes) for vertex- deletion problems on disk graphs, which results in EPTASes for many fundamental problems including VERTEX COVER, FEEDBACK VERTEX SET, SMALL CYCLE HITTING (in particular, TRIANGLE HITTING), Pk-VERTEX DELETION for k ∈ {3,4,5}, PATH DELETION, PATHWIDTH 1-DELETION, COMPONENT ORDER CONNECTIVITY, BOUNDED DEGREE DELETION, PSEUDOFOREST DELETION, FINITE-TYPE COMPONENT DELETION, etc. All EPTASes obtained using our framework are robust in the sense that they do not require a realization of the input disk graph (in fact, we allow the input to be any graph, and our algorithms either output a correct approximation solution for the problem or conclude that the input graph is not a disk graph). To the best of our knowledge, prior to this work, the only problems known to admit PTASes or EPTASes on disk graphs are MAXIMUM CLIQUE, INDEPENDENT SET, DOMINATING SET, and VERTEX COVER, among which the existing PTAS [Erlebach et al., SICOMP'05] and EPTAS [Leeuwen, SWAT'06] for VERTEX COVER require a realization of the input disk graph (while ours does not). The core of our framework is a reduction for a broad class of (approximation) vertex-deletion problems from (general) disk graphs to disk graphs of bounded local radius, which is a new invariant of disk graphs introduced in this work. Disk graphs of bounded local radius can be viewed as a “mild” generalization of planar graphs, which preserves certain nice properties of planar graphs. Specifically, we prove that disk graphs of bounded local radius admit the Excluded Grid Minor property and have locally bounded treewidth. This allows existing techniques for designing approximation schemes on planar graphs (e.g., bidimensionality and Baker's technique) to be directly applied to disk graphs of bounded local radius. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.02717

Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set X of n points and two numbers k, m, the clustering with outliers aims to exclude m points from X and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m—i.e., an algorithm with running time of the form f(k, m) · nO(1) for some function f—that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-Median and k-Means with outliers in general and Euclidean metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.

Approximate query processing (AQP) is one of the key techniques to cope with big data querying problem on account that it obtains approximate answers efficiently. To address non-trivial sample selection and heavy sampling cost issues in AQP, we propose ShadowAQP, an efficient and accurate approach based on attribute-oriented sample size allocation and data generation. We select samples according to group-by and join attributes, and determine the sample size for each group of unique value combinations to improve query accuracy. We design a conditional variational autoencoder model with automatic table data encoding and model update strategies. To further improve accuracy and efficiency, we propose a set of extensions, including parallel multi-round sampling aggregation, data outlier-aware sampling, and dimension reduction optimization. Evaluation results on diversified datasets show that, compared with SOTA approaches, ShadowAQP achieves 5.8× query speed performance improvement on average (up to 12.8×), while reducing query error by 74% on average (up to 95%) at the same time.

Suppose we are given a pair of points $s, t$ and a set $S$ of $n$ geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (multi-)graph $G$ with vertex set $S$ and every edge labeled from $\{0, 1\}$, such that a set $S_d \subseteq S$ of obstacles separates $s$ from $t$ if and only if $G[S_d]$ contains a cycle whose sum of labels is odd. Using this structural characterization of separating sets of obstacles we obtain the following algorithmic results. In the Obstacle-Removal problem the task is to find a curve in the plane connecting s to t intersecting at most q obstacles. We give a $2.3146^qn^{O(1)}$ algorithm for Obstacle-Removal, significantly improving upon the previously best known $q^{O(q^3)} n^{O(1)}$ algorithm of Eiben and Lokshtanov (SoCG'20). We also obtain an alternative proof of a constant factor approximation algorithm for Obstacle-Removal, substantially simplifying the arguments of Kumar et al. (SODA'21). In the Generalized Points-Separation problem, the input consists of the set S of obstacles, a point set A of k points and p pairs $(s_1, t_1),... (s_p, t_p)$ of points from A. The task is to find a minimum subset $S_r \subseteq S$ such that for every $i$, every curve from $s_i$ to $t_i$ intersects at least one obstacle in $S_r$. We obtain $2^{O(p)} n^{O(k)}$-time algorithm for Generalized Points-Separation problem. This resolves an open problem of Cabello and Giannopoulos (SoCG'13), who asked about the existence of such an algorithm for the special case where $(s_1, t_1), ... (s_p, t_p)$ contains all the pairs of points in A. Finally, we improve the running time of our algorithm to $f(p,k) n^{O(\sqrt{k})}$ when the obstacles are unit disks, where $f(p,k) = 2^O(p) k^{O(k)}$, and show that, assuming the Exponential Time Hypothesis (ETH), the running time dependence on $k$ of our algorithms is essentially optimal.

We consider multiwinner elections in Euclidean space using the minimax Chamberlin-Courant rule. In this setting, voters and candidates are embedded in a d-dimensional Euclidean space, and the goal is to choose a committee of k candidates so that the rank of any voter's most preferred candidate in the committee is minimized. (The problem is also equivalent to the ordinal version of the classical k-center problem.) We show that the problem is NP-hard in any dimension d >= 2, and also provably hard to approximate. Our main results are three polynomial-time approximation schemes, each of which finds a committee with provably good minimax score. In all cases, we show that our approximation bounds are tight or close to tight. We mainly focus on the 1-Borda rule but some of our results also hold for the more general r-Borda.

We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on H-minor free graphs. In particular, we obtain the following results (where k is the solution-size parameter). time algorithms for Edge Bipartization and Odd Cycle Transversal; a time algorithm for Edge Multiway Cut and a time algorithm for Vertex Multiway Cut (with undeletable terminals), where r is the number of terminals to be separated; a time algorithm for Edge Multicut and a time algorithm for Vertex Multicut (with undeletable terminals), where r is the number of terminal pairs to be separated; a time algorithm for Group Feedback Edge Set and a time algorithm for Group Feedback Vertex Set, where g is the size of the group. In addition, our approach also gives time algorithms for all above problems with the exception of time for Edge/Vertex Multicut and time for Group Feedback Edge/Vertex Set. All of our FPT algorithms (the first four items above) are randomized, as they use known randomized kernelization algorithms as sub-routines. We obtain our results by giving a new decomposition theorem on graphs of bounded genus, or more generally, an h-almost-embeddable graph for an arbitrary but fixed constant h. Our new decomposition theorem generalizes known Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010] and H-minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. In particular we show the following. Let G be a graph of bounded genus, or more generally, an h-almost-embeddable graph for an arbitrary but fixed constant h. Then for every p ∊ ℕ, there exist disjoint sets Z1, …, Zp ⊆ V(G) such that for every i ∊ {1, …, p} and every Z′ ⊆ Zi, the treewidth of G/(Zi\Z′) is upper bounded by O(p + |Z′|), where the constant hidden in O(·) depends on h. Here G/(Zi\Z′) denotes the graph obtained from G by contracting every edge with both endpoints in Zi\Z′. When Z′ = , this corresponds to classical Contraction Decomposition Theorem.

Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirement) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in 1D and 2D, which significantly improve and extend the previous results. Our results include the following: The first data structure for (1 + ∊)-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of O(log3 n/∊), improving the O(nδ/∊) bound of Agarwal et al. [SoCG'20], where δ > 0 denotes an arbitrarily small constant. A data structure for O(1)-approximate dynamic unit-square set cover with amortized update time, substantially improving the O(n1/2+δ) update time of Agarwal et al. [SoCG'20]. A data structure for O(1)-approximate dynamic square set cover with O(n1/2+δ) randomized amortized update time, improving the O(n2/3+δ) update time of Chan and He [SoCG'21]. A data structure for O(1)-approximate dynamic 2D halfplane set cover with O(n17/23+δ) randomized amortized update time. The previous solution for halfplane set cover by Chan and He [SoCG'21] is slower and can only report the size of the approximate solution. The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for (3 + o(1))-approximate dynamic weighted interval set cover with amortized update time and a data structure for O(1)-approximate dynamic weighted unit-square set cover with O(nδ) amortized update time.

One of the most celebrated results in Parameterized Complexity is the Bidimensionality theory of Demaine et al. [J. ACM, 2005], which has yielded, over the past two decades, numerous subexponential-time fixed-parameter tractable (FPT) algorithms for various problems on planar (and H-minor-free) graphs. At the heart of this theory is the proof of sublinear bounds in terms of solution size on the treewidth of a given graph. Inspired by this theory, in recent years, significant efforts have been devoted to design subexponential-time FPT algorithms for problems on geometric graph classes that utilize new treewidth bounds, in particular (but not only) for unit disk graphs [Fomin et al., SODA'12; Fomin et al., DCG'19; Panolan et al., SODA'19; Fomin et al. SoCG'20]. In this paper, we aim to attain such results on disk graphs, a broad class of graphs that generalizes both the classes of planar graphs and unit disk graphs, and thereby unify the aforementioned research frontiers for planar and unit disk graphs. Our main contribution is an approach to design subexponential-time FPT algorithms for problems on disk graphs, which we apply to several well-studied graph problems. At the heart of our approach lie two new combinatorial theorems concerning the treewidth of disk graphs having a realization of bounded ply (or maximum clique size) that are of independent interest. In particular, we prove a stronger version of the following treewidth bound: Let G be a disk graph that has some realization of ply p and no false twins, and M ⊆ V(G) such that G has no triangle with exactly one vertex from M, and G–M has treewidth w. Then, the treewidth of G is . Among our applications are the first subexponential-time FPT algorithms for several problems on disk graphs, including Triangle Hitting, Feedback Vertex Set and Odd Cycle Transversal (OCT). Previously, subexponential-time FPT algorithms for these problems were only known on planar graphs and unit disk graphs (excluding OCT, which was only known to admit such an algorithm on planar graphs). Our algorithms are robust, in particular, they do not require a geometric realization of the input graph (for all aforementioned problems), and they generalize to the weighted and counting versions of all aforementioned problems except for OCT.

We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our article are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in ℝ 1 and ℝ 2 . The first framework uses bootstrapping and gives a (1 + ε)-approximate data structure for dynamic interval set cover in ℝ 1 with O ( n α / ε) amortized update time for any constant α > 0; in ℝ 2 , this method gives O (1)-approximate data structures for unit-square set cover and hitting set with O ( n 1/2+α ) amortized update time. The second framework uses local modification and leads to a (1 + ε)-approximate data structure for dynamic interval hitting set in ℝ 1 with Õ(1/ε) amortized update time; in ℝ 2 , it gives O (1)-approximate data structures for unit-square set cover and hitting set in the partially dynamic settings with Õ(1) amortized update time.

In the Multi-Team Formation problem, we are given a ground set C of n candidates, each of which is characterized by a d-dimensional attribute vector in ℝ^d, and two positive integers α and β satisfying α β ≤ n. The goal is to form α disjoint teams T₁,...,T_α ⊆ C, each of which consists of β candidates in C, such that the total score of the teams is maximized, where the score of a team T is the sum of the h_j maximum values of the j-th attributes of the candidates in T, for all j ∈ {1,...,d}. Our main result is an 2^{2^O(d)} n^O(1)-time algorithm for Multi-Team Formation. This bound is ETH-tight since a 2^{2^{d/c}} n^O(1)-time algorithm for any constant c > 12 can be shown to violate the Exponential Time Hypothesis (ETH). Our algorithm runs in polynomial time for all dimensions up to d = clog log n for a sufficiently small constant c > 0. Prior to our work, the existence of a polynomial time algorithm was an open problem even for d = 3.

We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in $\mathbb{R}^1$ and $\mathbb{R}^2$. The first framework uses bootstrapping and gives a $(1+\varepsilon)$-approximate data structure for dynamic interval set cover in $\mathbb{R}^1$ with $O(n^α/\varepsilon)$ amortized update time for any constant $α> 0$; in $\mathbb{R}^2$, this method gives $O(1)$-approximate data structures for unit-square (and quadrant) set cover and hitting set with $O(n^{1/2+α})$ amortized update time. The second framework uses local modification, and leads to a $(1+\varepsilon)$-approximate data structure for dynamic interval hitting set in $\mathbb{R}^1$ with $\widetilde{O}(1/\varepsilon)$ amortized update time; in $\mathbb{R}^2$, it gives $O(1)$-approximate data structures for unit-square (and quadrant) set cover and hitting set in the \textit{partially} dynamic settings with $\widetilde{O}(1)$ amortized update time.

We revisit a classical graph-theoretic problem, the single-source shortest-path (SSSP) problem, in weighted unit-disk graphs. We first propose an exact (and deterministic) algorithm which solves the problem in O(n log^2 n) time using linear space, where n is the number of the vertices of the graph. This significantly improves the previous deterministic algorithm by Cabello and Jejčič [CGTA'15] which uses O(n^{1+delta}) time and O(n^{1+delta}) space (for any small constant delta>0) and the previous randomized algorithm by Kaplan et al. [SODA'17] which uses O(n log^{12+o(1)} n) expected time and O(n log^3 n) space. More specifically, we show that if the 2D offline insertion-only (additively-)weighted nearest-neighbor problem with k operations (i.e., insertions and queries) can be solved in f(k) time, then the SSSP problem in weighted unit-disk graphs can be solved in O(n log n+f(n)) time. Using the same framework with some new ideas, we also obtain a (1+epsilon)-approximate algorithm for the problem, using O(n log n + n log^2(1/epsilon)) time and linear space. This improves the previous (1+epsilon)-approximate algorithm by Chan and Skrepetos [SoCG'18] which uses O((1/epsilon)^2 n log n) time and O((1/epsilon)^2 n) space. Because of the Omega(n log n)-time lower bound of the problem (even when approximation is allowed), both of our algorithms are almost optimal.

We consider a range-search variant of the closest-pair problem. Let Gamma be a fixed shape in the plane. We are interested in storing a given set of n points in the plane in some data structure such that for any specified translate of Gamma, the closest pair of points contained in the translate can be reported efficiently. We present results on this problem for two important settings: when Gamma is a polygon (possibly with holes) and when Gamma is a general convex body whose boundary is smooth. When Gamma is a polygon, we present a data structure using O(n) space and O(log n) query time, which is asymptotically optimal. When Gamma is a general convex body with a smooth boundary, we give a near-optimal data structure using O(n log n) space and O(log^2 n) query time. Our results settle some open questions posed by Xue et al. at SoCG 2018.

The range closest-pair (RCP) problem is the range-search version of the classical closest-pair problem, which aims to store a given dataset of points in some data structure such that when a query range X is specified, the closest pair of points contained in X can be reported efficiently. A natural generalization of the RCP problem is the colored range closest-pair (CRCP) problem in which the given data points are colored and the goal is to find the closest bichromatic pair contained in the query range. All the previous work on the RCP problem was restricted to the uncolored version and the Euclidean distance function. In this paper, we make the first progress on the CRCP problem. We investigate the problem under a general distance function induced by a monotone norm; in particular, this covers all the Lp-metrics for p ≥ 1 and the L∞-metric. We design efficient (1+ε)-approximate CRCP data structures for orthogonal queries in ℝ, where ε > 0 is a pre-specified parameter. The highlights are two data structures for answering rectangle queries, one of which uses O(ε−1 n log4 n) space and O(log4 n + ε−1 log3 n + ε−2 log n) query time while the other uses O(ε−1 n log3 n) space and O(log5 n + ε−1 log4 n + ε−2 log2 n) query time, where n is the size of the input dataset. In addition, we also apply our techniques to the CRCP problem in higher dimensions, obtaining efficient data structures for slab, 2-box, and 3D dominance queries. Before this paper, almost all the existing results for the RCP problem were achieved in ℝ2.

Given a dataset S of points in R^2, the range closest-pair (RCP) problem aims to preprocess S into a data structure such that when a query range X is specified, the closest-pair in S cap X can be reported efficiently. The RCP problem can be viewed as a range-search version of the classical closest-pair problem, and finds applications in many areas. Due to its non-decomposability, the RCP problem is much more challenging than many traditional range-search problems. This paper revisits the RCP problem, and proposes new data structures for various query types including quadrants, strips, rectangles, and halfplanes. Both worst-case and average-case analyses (in the sense that the data points are drawn uniformly and independently from the unit square) are applied to these new data structures, which result in new bounds for the RCP problem. Some of the new bounds significantly improve the previous results, while the others are entirely new.

In this paper, we study the linear separability problem for stochastic geometric objects under the well-known unipoint/multipoint uncertainty models. Let S=S_R U S_B be a given set of stochastic bichromatic points, and define n = min{|S_R|, |S_B|} and N = max{|S_R|, |S_B|}. We show that the separable-probability (SP) of S can be computed in O(nN^{d-1}) time for d >= 3 and O(min{nN log N, N^2}) time for d=2, while the expected separation-margin (ESM) of S can be computed in O(nN^d) time for d >= 2. In addition, we give an Omega(nN^{d-1}) witness-based lower bound for computing SP, which implies the optimality of our algorithm among all those in this category. Also, a hardness result for computing ESM is given to show the difficulty of further improving our algorithm. As an extension, we generalize the same problems from points to general geometric objects, i.e., polytopes and/or balls, and extend our algorithms to solve the generalized SP and ESM problems in O(nN^d) and O(nN^{d+1}) time, respectively. Finally, we present some applications of our algorithms to stochastic convex-hull related problems.