Search

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles. [ABSTRACT FROM AUTHOR]

We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1 polytopes and half-integral polytopes. [ABSTRACT FROM AUTHOR]

Tverberg's theorem states that for any k ≥ 2 and any set P ⊂ R d of at least (d + 1) (k - 1) + 1 points in d dimensions, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem of finding the partition lies in the complexity class CLS = PPAD ∩ PLS , but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa (SODA 2019) gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set P ⊂ R d and any k ∈ { 2 , ⋯ , n } in O (n d ⌈ log k ⌉) time a k-partition of P such that there is a ball of radius O ((k / n) diam (P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria's method (Israel Journal Math., 1992) to reduce the Tverberg problem to the colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem. [ABSTRACT FROM AUTHOR]

Inspired by the seminal works of Khuller et al. (SIAM J. Comput. 25(2), 355–368 (1996)) and Chan (Discrete Comput. Geom. 32(2), 177–194 (2004)) we study the bottleneck version of the Euclidean bounded-degree spanning tree problem. A bottleneck spanning tree is a spanning tree whose largest edge-length is minimum, and a bottleneck degree-K spanning tree is a degree-K spanning tree whose largest edge-length is minimum. Let β K be the supremum ratio of the largest edge-length of the bottleneck degree-K spanning tree to the largest edge-length of the bottleneck spanning tree, over all finite point sets in the Euclidean plane. It is known that β 5 = 1 , and it is easy to verify that β 2 ⩾ 2 , β 3 ⩾ 2 , and β 4 > 1.175 . It is implied by the Hamiltonicity of the cube of the bottleneck spanning tree that β 2 ⩽ 3 . The degree-3 spanning tree algorithm of Ravi et al. (25th Annual ACM Symposium on Theory of Computing, pp. 438–447. ACM, New York (1993)) implies that β 3 ⩽ 2 . Andersen and Ras (Networks 68(4), 302–314 (2016)) showed that β 4 ⩽ 3 . We present the following improved bounds: β 2 ⩾ 7 , β 3 ⩽ 3 , and β 4 ⩽ 2 . As a result, we obtain better approximation algorithms for Euclidean bottleneck degree-3 and degree-4 spanning trees. As parts of our proofs of these bounds we present some structural properties of the Euclidean minimum spanning tree which are of independent interest. [ABSTRACT FROM AUTHOR]

We consider a well-studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and a fixed parameter d ≥ 1 , in the maximum diameter-bounded subgraph problem (MaxDBS for short) the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d = 1 , this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n 1 - ϵ , for any ϵ > 0 . Moreover, it is known that, for any d ≥ 2 , it is NP-hard to approximate MaxDBS within a factor n 1 / 2 - ϵ , for any ϵ > 0 . In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems, and several geometric properties of unit disk graphs. [ABSTRACT FROM AUTHOR]

Given a set of n points in the plane, and a parameter k , we consider the problem of computing the minimum (perimeter or area) axis-aligned rectangle enclosing k points. We present the first near quadratic time algorithm for this problem, improving over the previous near- O (n 5 / 2) -time algorithm by Kaplan et al. (25th European Symposium on Algorithms. Leibniz Int Proc Inform, vol. 87, # 52. Leibniz-Zent Inform, Wadern, 2017). We provide an almost matching conditional lower bound, under the assumption that (min , +) -convolution cannot be solved in truly subquadratic time. Furthermore, we present a new reduction (for both perimeter and area) that can make the time bound sensitive to k , giving near O (n k) time. We also present a near linear time (1 + ε) -approximation algorithm to the minimum area of the optimal rectangle containing k points. In addition, we study related problems including the 3-sided, arbitrarily oriented, weighted, and subset sum versions of the problem. [ABSTRACT FROM AUTHOR]

Given a finite range space Σ = (X , R) , with N = | X | + | R | , we present two simple algorithms, based on the multiplicative-weight method, for computing a small-size hitting set or set cover of Σ . The first algorithm is a simpler variant of the Brönnimann–Goodrich algorithm but more efficient to implement, and the second algorithm can be viewed as solving a two-player zero-sum game. These algorithms, in conjunction with some standard geometric data structures, lead to near-linear algorithms for computing a small-size hitting set or set cover for a number of geometric range spaces. For example, they lead to O (N polylog (N)) expected-time randomized O(1)-approximation algorithms for both hitting set and set cover if X is a set of points and R a set of disks in R 2 . [ABSTRACT FROM AUTHOR]

We study the problem of guarding orthogonal art galleries with horizontal mobile guards (alternatively, vertical) and point guards, using "rectangular vision". We prove a sharp bound on the minimum number of point guards required to cover the gallery in terms of the minimum number of vertical mobile guards and the minimum number of horizontal mobile guards required to cover the gallery. Furthermore, we show that the latter two numbers can be computed in linear time. [ABSTRACT FROM AUTHOR]

Classical methods to model topological properties of point clouds, such as the Vietoris-Rips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multi-scale filtration of the Rips complex with improved bounds for size: precisely, for n points in Rd, we obtain a O(d)-approximation whose k-skeleton has size n2O(dlogk) per scale and n2O(dlogd) in total over all scales. In conjunction with dimension reduction techniques, our approach yields a O(polylog(n))-approximation of size nO(1) for Rips filtrations on arbitrary metric spaces. This result stems from high-dimensional lattice geometry and exploits properties of the permutahedral lattice, a well-studied structure in discrete geometry. Building on the same geometric concept, we also present a lower bound result on the size of an approximation: we construct a point set for which every (1+ε)-approximation of the Čech filtration has to contain nΩ(loglogn) features, provided that ε<1log1+cn for c∈(0,1). [ABSTRACT FROM AUTHOR]

In this paper, we design the first polynomial time approximation schemes for the Set Cover and Dominating Set problems when the underlying sets are non-piercing regions (which include pseudodisks). Earlier, PTASs were known only in the setting where the regions were disks. These techniques relied heavily on the circularity of the disks. We develop new techniques to show that a simple local search algorithm yields a PTAS for the problems on non-piercing regions. We then consider the Capacitated Region Packing problem. Here, the input consists of a set of points with capacities, and a set of regions. The objective is to pick a maximum cardinality subset of regions so that no point is covered by more regions than its capacity. We show that this problem admits a PTAS when the regions are k-admissible regions (pseudodisks are 2-admissible), and the capacities are bounded by some constant. Our result settles a conjecture of Har-Peled from 2014 in the affirmative. The conjecture was for a weaker version of the problem, namely when the regions are pseudodisks, the capacities are uniform, and the point set consists of all points in the plane. Finally, we consider the Capacitated Point Packing problem. In this setting, the regions have capacities, and our objective is to find a maximum cardinality subset of points such that no region has more points than its capacity. We show that this problem admits a PTAS when the capacity is unity. This extends a result of Ene et al. from 2012. [ABSTRACT FROM AUTHOR]

The Gromov-Hausdorff distance of two compact metric spaces is a measure for how far the spaces are from being isometric and has been extensively studied in the field of metric geometry. In recent years, a lot of attention has been devoted to computational aspects of the Gromov-Hausdorff distance. One of the most prominent applications is the problem of shape matching, where the goal is to decide whether two shapes given as polygonal meshes are equivalent under certain invariances. Therefore, many methods have been proposed which heuristically estimate the Gromov-Hausdorff distance of metric spaces induced by the shapes. However, the computational complexity of computing the Gromov-Hausdorff distance has not yet been thoroughly investigated. We show that-under standard complexity theoretic assumptions-determining the Gromov-Hausdorff distance of two finite metric spaces cannot be approximated within any reasonable bound in polynomial time. Furthermore, we discover attributes of metric spaces which have a major impact on the complexity of an instance. This enables us to develop an approximation algorithm which is fixed parameter tractable with respect to corresponding parameters. [ABSTRACT FROM AUTHOR]

Over the past several decades there has been steady progress towards the goal of polynomial-time approximation schemes (PTAS) for fundamental geometric combinatorial optimization problems. A foremost example is the geometric hitting set problem: given a set P of points and a set $$\mathcal {D}$$ of geometric objects, compute the minimum-sized subset of P that hits all objects in $$\mathcal {D}$$ . For the case where $$\mathcal {D}$$ is a set of disks in the plane, the 30-year quest for a PTAS, starting from the seminal work of Hochbaum (SIAM J Comput 11:555-556, 1982), was finally achieved in Mustafa and Ray (Discret Comput Geom 44:883-895, 2010). Surprisingly, the algorithm to achieve the PTAS is simple: local-search. In particular, the algorithm starts with any hitting set, and iteratively tries to decrease its size by trying to replace some k points by $$k-1$$ points; call such an algorithm a $$(k, k-1)$$ -local search algorithm. Since then, local-search has turned out to be a powerful algorithmic approach towards achieving good approximation ratios for geometric problems (for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others). Unfortunately all these algorithms have the same limitation: local search is able to give a PTAS, but with large running times. In particular, the current best work shows that if $$k \ge 30$$ , then local-search is able to give a constant factor (as a function of k) approximation ratio (Fraser in Algorithms for Geometric Covering and Piercing Problems, 2012). Unfortunately this then implies that the running time for local-search to provably work at all is $$\Omega (n^{30})$$ using the current framework. As currently local search is the only known method that gives approximation factors that could be useful in practice, it becomes important to explore the limits-in both efficiency and quality-of local search. Simple examples show that (1, 0) and (2, 1) local search cannot give constant factor approximations. In this paper, we show that, surprisingly, just (3, 2) local search is able to give a constant-factor approximation; in fact we are able to get the precise quality limit of (3, 2)-local search: factor 8 approximation. This simplest working instance of local search already gives an approximation factor that is better than all known other methods! In fact, our improvement applies to all algorithms that use local-search for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others. Finding efficient (3, 2)-local search algorithms then becomes the key bottleneck in efficient and good-quality algorithms. In this paper we present such improved algorithms. [ABSTRACT FROM AUTHOR]

We investigate what computational tasks can be performed on a point set in $${\mathbb {R}}^d$$ , if we are only given black-box access to it via nearest-neighbor search. This is a reasonable assumption if the underlying point set is either provided implicitly, or it is stored in a data structure that can answer such queries. In particular, we show the following: We also investigate the problem of clustering the given point set, such that meaningful proximity queries can be carried out on the centers of the clusters, instead of the whole point set. [ABSTRACT FROM AUTHOR]

We extend and unify most known results about guarding orthogonal polygons by introducing the same-sign diagonal graphs of a convex quadrangulation and applying results about vertex covers for graphs. Our approach also yields new theorems and often guarantees two disjoint vertex guard sets of relatively small cardinality. For instance, an orthogonal polygon on n vertices has two disjoint vertex guard sets of cardinality at most $$\lfloor n/4\rfloor $$ . We give new proofs of Aggarwal's one-hole theorem and the orthogonal fortress theorem. We prove that an orthogonal polygon with n vertices and any number of holes can be protected by at most $$\lfloor (17n-8)/52\rfloor $$ vertex guards, improving the best known bound of $$\lfloor n/3\rfloor $$ . Also, an orthogonal polygon with n vertices and h holes can be protected by $$\lfloor (n+2h)/3\rfloor $$ guarded guards, which is best possible when $$n\ge 16h$$ . Moreover, for orthogonal fortresses with n vertices, $$\lfloor (n+6)/3\rfloor $$ guarded guards are always sufficient and sometimes necessary. [ABSTRACT FROM AUTHOR]

We describe a $$O(\log n )$$ -approximation algorithm for computing the homotopic Fréchet distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms were known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a $$O(\log n)$$ -approximation algorithm for computing the minimum height of a homotopy between two curves. No algorithms were previously known for approximating this parameter. Surprisingly, it is not even known if computing either the homotopic Fréchet distance, or the minimum height of a homotopy, is in NP. [ABSTRACT FROM AUTHOR]

We consider a generalization of the familiar art gallery problem in which individual points within the gallery need to be visible to some specified, but not necessarily uniform, number of guards. We provide an $$O(\lg \lg {\mathrm {OPT}})$$ -approximation algorithm for this multi-guarding problem in simply-connected polygonal regions, with a minimum number ( $${\mathrm {OPT}}$$ ) of vertex guards (possibly co-located). Our approximation algorithm is based on a polynomial-time algorithm for building what we call $$\varepsilon $$ -multinets of size $$O\left( \frac{1}{\varepsilon }\lg \lg \frac{1}{\varepsilon }\right) $$ for the instances of Multi- HittingSet associated with our multi-guarding problem. We then apply a now-standard linear-programming technique to build an approximation algorithm from this $$\varepsilon $$ -multinet finder. This paper corrects, and simplifies the analysis of, the $$O\left( \frac{1}{\varepsilon }\lg \lg \frac{1}{\varepsilon }\right) $$ -time $$\varepsilon $$ -net-finder described in [], that was used to build an $$O(\lg \lg {\mathrm {OPT}})$$ -approximation algorithm for the standard guarding problem in which all points within the gallery are required to be visible to at least one guard. [ABSTRACT FROM AUTHOR]

The problem of maximizing the $$p$$ th power of a $$p$$ -norm over a halfspace-presented polytope in $$\mathbb {R}^d$$ is a convex maximization problem which plays a fundamental role in computational convexity. Mangasarian and Shiau showed in 1986 that this problem is $$\mathbb {NP}$$ -hard for all values $$p \in \mathbb {N}$$ if the dimension $$d$$ of the ambient space is part of the input. In this paper, we use the theory of parameterized complexity to analyze how heavily the hardness of norm maximization relies on the parameter $$d$$ . More precisely, we show that for $$p=1$$ the problem is fixed-parameter tractable (in FPT for short) but that for all $$p >1$$ norm maximization is W[1]-hard. Concerning approximation algorithms for norm maximization, we show that, for fixed accuracy, there is a straightforward approximation algorithm for norm maximization in FPT running time, but there is no FPT-approximation algorithm with a running time depending polynomially on the accuracy. As with the $$\mathbb {NP}$$ -hardness of norm maximization, the W[1]-hardness immediately carries over to various radius computation tasks in computational convexity. [ABSTRACT FROM AUTHOR]

Given a set of $$n$$ axis-parallel rectangles in the plane, finding a maximum independent set ( $$\mathrm {MIS}$$ ), a maximum weighted independent set ( $$\mathrm {WMIS}$$ ), and a minimum hitting set ( $$\mathrm {MHS}$$ ), are basic problems in computational geometry and combinatorics. They have attracted significant attention since the sixties, when Wegner conjectured that the duality gap, equal to the ratio between the size of $$\mathrm {MIS}$$ and the size of $$\mathrm {MHS}$$ , is always bounded by a universal constant. An interesting case is when there exists a diagonal line that intersects each of the given rectangles. Indeed, Chepoi and Felsner recently gave a 6-approximation algorithm for $$\mathrm {MHS}$$ in this setting, and showed that the duality gap is between 3/2 and 6. We consider the same setting and improve upon these results. First, we derive an $$O(n^2)$$ -time algorithm for the $$\mathrm {WMIS}$$ when, in addition, every pair of intersecting rectangles have a common point below the diagonal. This improves and extends a classic result of Lubiw, and gives a 2-approximation algorithm for $$\mathrm {WMIS}$$ . Second, we show that $$\mathrm {MIS}$$ is NP-hard. Finally, we prove that the duality gap is between 2 and 4. The upper bound, which implies a 4-approximation algorithm for $$\mathrm {MHS}$$ , follows from simple combinatorial arguments, whereas the lower bound represents the best known lower bound on the duality gap, even in the general setting of the rectangles. [ABSTRACT FROM AUTHOR]

Given points in Euclidean space of arbitrary dimension, we prove that there exists a spanning tree having no vertices of degree greater than 3 with weight at most 1.559 times the weight of the minimum spanning tree. We also prove that there is a set of points such that no spanning tree of maximal degree 3 exists that has this ratio be less than 1.447. Our central result is based on the proof of the following claim: Given n points in Euclidean space with one special point v, there exists a Hamiltonian path with an endpoint at v that is at most 1.559 times longer than the sum of the distances of the points to v. These proofs also lead to a way to find the tree in linear time given the minimal spanning tree. [ABSTRACT FROM AUTHOR]

We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $$\mathcal D $$ , consisting of $$n$$ tetrahedra with positive weights, and a real number $$\varepsilon \in (0,1)$$ , our algorithm constructs paths in $$\mathcal D $$ from a fixed source vertex to all vertices of $$\mathcal D $$ , the costs of which are at most $$1+\varepsilon $$ times the costs of (weighted) shortest paths, in $$O(\mathcal{C }(\mathcal D )\frac{n}{\varepsilon ^{2.5}}\log \frac{n}{\varepsilon }\log ^3\frac{1}{\varepsilon })$$ time, where $$\mathcal{C }(\mathcal D )$$ is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25-53, ), to three dimensions. [ABSTRACT FROM AUTHOR]

This paper deals with the containment problem under homothetics which has the minimal enclosing ball (MEB) problem as a prominent representative. We connect the problem to results in classic convex geometry and introduce a new series of radii, which we call core-radii. For the MEB problem, these radii have already been considered from a different point of view and sharp inequalities between them are known. In this paper sharp inequalities between core-radii for general containment under homothetics are obtained. Moreover, the presented inequalities are used to derive sharp upper bounds on the size of core-sets for containment under homothetics. In the MEB case, this yields a tight (dimension-independent) bound for the size of such core-sets. In the general case, we show that there are core-sets of size linear in the dimension and that this bound stays sharp even if the container is required to be symmetric. [ABSTRACT FROM AUTHOR]

Given a continuous function f: X→ℝ on a topological space X, its level set f( a) changes continuously as the real value a changes. Consequently, the connected components in the level sets appear, disappear, split and merge. The Reeb graph of f summarizes this information into a graph structure. Previous work on Reeb graph mainly focused on its efficient computation. In this paper, we initiate the study of two important aspects of the Reeb graph, which can facilitate its broader applications in shape and data analysis. The first one is the approximation of the Reeb graph of a function on a smooth compact manifold M without boundary. The approximation is computed from a set of points P sampled from M. By leveraging a relation between the Reeb graph and the so-called vertical homology group, as well as between cycles in M and in a Rips complex constructed from P, we compute the H-homology of the Reeb graph from P. It takes O( nlog n) expected time, where n is the size of the 2-skeleton of the Rips complex. As a by-product, when M is an orientable 2-manifold, we also obtain an efficient near-linear time (expected) algorithm for computing the rank of H( M) from point data. The best-known previous algorithm for this problem takes O( n) time for point data. The second aspect concerns the definition and computation of the persistent Reeb graph homology for a sequence of Reeb graphs defined on a filtered space. For a piecewise-linear function defined on a filtration of a simplicial complex K, our algorithm computes all persistent H-homology for the Reeb graphs in $O(n n_{e}^{3})$ time, where n is the size of the 2-skeleton and n is the number of edges in K. [ABSTRACT FROM AUTHOR]

We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local-search algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, which leads to a constant-factor approximation. Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest. [ABSTRACT FROM AUTHOR]

We present a simple and practical (1+ ε)-approximation algorithm for the Fréchet distance between two polygonal curves in ℝ. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and similar results for other input models, such as low-density polygonal curves. [ABSTRACT FROM AUTHOR]

We consider the problem of fitting a subspace of a specified dimension k to a set P of n points in ℝ. The fit of a subspace F is measured by the L norm, that is, it is defined as the τ-root of the sum of the τth powers of the Euclidean distances of the points in P from F, for some τ≥1. Our main result is a randomized algorithm that takes as input P, k, and a parameter 0< ε<1; runs in $nd \cdot2^{O(\frac{\tau k^{2}}{\varepsilon} \log^{2} \frac {k}{\varepsilon})}$ time, and returns a k-subspace that with probability at least 1/2 has a fit that is at most (1+ ε) times that of the optimal k-subspace. [ABSTRACT FROM AUTHOR]

In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and simplifying the factor 100 and 27 algorithms of Bǎdoiu et al. (Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms (SODA 2007), pp. 512-521, ) and Bǎdoiu et al. (Proceedings of the 11th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2008), Springer, Berlin, pp. 21-34, )). We also present a constant factor algorithm for approximating the optimal distortion of embedding a graph metric into an outerplanar metric. For this, we introduce a general notion of a metric relaxed minor and show that if G contains an α-metric relaxed H-minor, then the distortion of any embedding of G into any metric induced by a H-minor free graph is ≥ α. Then, for H= K, we present an algorithm which either finds an α-relaxed minor, or produces an O( α)-embedding into an outerplanar metric. [ABSTRACT FROM AUTHOR]

We provide an O(log log opt)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building ε-nets of size $O(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon})$ for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Brönnimann and Goodrich to build an approximation algorithm from this ε-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon's vertices. If a finite set of potential guard locations is not specified, e.g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm's running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log opt)-approximation algorithms that use generic net finders for set systems of finite VC-dimension. [ABSTRACT FROM AUTHOR]

Given a set T of n points in ℝ, a Manhattan network on T is a graph G with the property that for each pair of points in T, G contains a rectilinear path between them of length equal to their distance in the L-metric. The minimum Manhattan network problem is to find a Manhattan network of minimum length, i.e., minimizing the total length of the line segments in the network. In this paper, we prove that the decision version of the MMN problem is strongly NP-complete, using a reduction from the well-known 3-SAT problem, which requires a number of gadgets. The gadgets have similar structures, but play different roles in simulating a 3-CNF formula. [ABSTRACT FROM AUTHOR]

We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P = NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in ℝ and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local-search algorithm which iterates over local improvements only. [ABSTRACT FROM AUTHOR]

We consider the well-known geometric problem of determining shortest paths between pairs of points on a polyhedral surface P, where P consists of triangular faces with positive weights assigned to them. The cost of a path in P is defined to be the weighted sum of Euclidean lengths of the sub-paths within each face of P. We present query algorithms that compute approximate distances and/or approximate shortest paths on P. Our all-pairs query algorithms take as input an approximation parameter ε∈(0,1) and a query time parameter $\mathfrak{q}$ , in a certain range, and build a data structure $\mathrm{APQ}(P,\varepsilon;\mathfrak{q})$ , which is then used for answering ε-approximate distance queries in $O(\mathfrak{q})$ time. As a building block of the $\mathrm{APQ}(P,\varepsilon;\mathfrak{q})$ data structure, we develop a single-source query data structure SSQ( a; P, ε) that can answer ε-approximate distance queries from a fixed point a to any query point on P in logarithmic time. Our algorithms answer shortest path queries in weighted surfaces, which is an important extension, both theoretically and practically, to the extensively studied Euclidean distance case. In addition, our algorithms improve upon previously known query algorithms for shortest paths on surfaces. The algorithms are based on a novel graph separator algorithm introduced and analyzed here, which extends and generalizes previously known separator algorithms. [ABSTRACT FROM AUTHOR]

We revisit some maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, ). Given a set of n points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching, (b) a Hamiltonian path, and (c) a spanning tree. We obtain some new results for (b) and (c), as well as for the Hamiltonian cycle problem. (i) For the longest non-crossing Hamiltonian path problem, we give an approximation algorithm with ratio $\frac{2}{\pi+1}\approx0.4829$. The previous best ratio, due to Alon et al., was $\frac{1}{\pi }\approx0.3183$. The ratio of our algorithm is close to $\frac{2}{\pi}\approx0.6366$ on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. For instance 'random' point sets meet the condition with high probability. The algorithm runs in O( nlog n) time. (ii) For the longest non-crossing spanning tree problem, we give an approximation algorithm with ratio 0.502 which runs in O( nlog n) time. The previous ratio, 1/2, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first re-derive the result of Alon et al. with a faster algorithm and a very simple analysis. (iii) For the longest non-crossing Hamiltonian cycle problem, we give an approximation algorithm whose ratio is close to 2/ π on a relatively broad class of instances: for point sets where the product 〈diameter×convex hull size〉 is much smaller than the maximum length matching. Again 'random' point sets meet the condition with high probability. However, this algorithm does not come with a constant approximation guarantee for all instances. The algorithm runs in O( nlog n) time. No previous approximation results were known for this problem. [ABSTRACT FROM AUTHOR]

We show that for every n-point metric space M and positive integer k, there exists a spanning tree T with unweighted diameter O( k) and weight w( T)= O( k⋅ n1/ k)⋅ w( MST( M)), and a spanning tree T′ with weight w( T′)= O( k)⋅ w( MST( M)) and unweighted diameter O( k⋅ n1/ k). These trees also achieve an optimal maximum degree. Furthermore, we demonstrate that these trees can be constructed efficiently. We prove that these tradeoffs between unweighted diameter and weight are tight up to constant factors in the entire range of parameters. Moreover, our lower bounds apply to a basic one-dimensional Euclidean space. Our lower bounds for the particular case of unweighted diameter O(log n) are of independent interest, settling a long-standing open problem in Computational Geometry. In STOC’95 Arya et al. devised a construction of Euclidean Spanners with unweighted diameter O(log n) and weight O(log n)⋅ w( MST( M)). In SODA’05 Agarwal et al. showed that this result is tight up to a factor of O(log log n). We close this gap and show that the result of Arya et al. is tight up to constant factors. Finally, our upper bounds imply improved approximation algorithms for the minimum h -hop spanning tree and bounded diameter minimum spanning tree problems for metric spaces. [ABSTRACT FROM AUTHOR]

We give a dynamic data structure that can maintain an ε-coreset of n points, with respect to the extent measure, in O(log n) time per update for any constant ε>0 and any constant dimension. The previous method by Agarwal, Har-Peled, and Varadarajan requires polylogarithmic update time. For points with integer coordinates bounded by U, we alternatively get O(log log U) time. Numerous applications follow, for example, on dynamically approximating the width, smallest enclosing cylinder, minimum bounding box, or minimum-width annulus. We can also use the same approach to maintain approximate k-centers in time O(log n) (or O(log log U) if the spread is bounded by U) for any constant k and any constant dimension. For the smallest enclosing cylinder problem, we also show that a constant-factor approximation can be maintained in O(1) randomized amortized time on the word RAM. [ABSTRACT FROM AUTHOR]

We improve the previous results by Aronov and Har-Peled (SODA’05) and Kaplan and Sharir (SODA’06) and present a randomized data structure of O( n) expected size which can answer 3D approximate halfspace range counting queries in $O(\log{n\over k})$ expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo. In addition, we describe new results for several related problems, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions. [ABSTRACT FROM AUTHOR]

In Rao (Proceedings of the 15th Annual Symposium on Computational Geometry, pp. 300–306, ), it is shown that every n-point Euclidean metric with polynomial aspect ratio admits a Euclidean embedding with k-dimensional distortion bounded by $O(\sqrt{\log n\log k})$ , a result which is tight for constant values of k. We show that this holds without any assumption on the aspect ratio and give an improved bound of $O(\sqrt{\log n}(\log k)^{1/4})$ . Our main result is an upper bound of $O(\sqrt{\log n}\log\log n)$ independent of the value of k, nearly resolving the main open questions of Dunagan and Vempala (Randomization, Approximation, and Combinatorial Optimization, pp. 229–240, ) and Krauthgamer et al. (Discrete Comput. Geom. 31(3):339–356, ). The best previous bound was O(log n), and our bound is nearly tight, as even the two-dimensional volume distortion of an n-vertex path is $\Omega(\sqrt{\log n})$ . [ABSTRACT FROM AUTHOR]

Given a finite set of points S in ℝ d, consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has the minimum number of segments (links). We call this minimization problem the minimum link spanning path problem. This natural problem has appeared several times in the literature under different variants. The simplest one is that in which the allowed paths are axis-aligned. Let L( S) be the minimum number of links of an axis-aligned path for S, and let G be an n×...× n grid in ℤ d. Kranakis et al. (Ars Comb. 38:177–192, ) showed that L( G)=2 n−1 and $\frac{4}{3}n^{2}-O(n)\le L(G^{3}_{n})\le \frac{3}{2}n^{2}+O(n)$ and conjectured that, for all d≥3, $L(G^{d}_{n})=\frac{d}{d-1}n^{d-1}\pm O(n^{d-2}).$ We prove the conjecture for d=3 by showing the lower bound for L( G). For d=4, we prove that $L(G^{4}_{n})=\frac{4}{3}n^{3}\pm O(n^{5/2}).$ For general d, we give new estimates on L( G) that are very close to the conjectured value. The new lower bound of $(1+\frac{1}{d})n^{d-1}-O(n^{d-2})$ improves previous result by Collins and Moret (Inf. Process. Lett. 68:317–319, ), while the new upper bound of $(1+\frac{1}{d-1})n^{d-1}+O(n^{d-3/2})$ differs from the conjectured value only in the lower order terms. For arbitrary point sets, we include an exact bound on the minimum number of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in ℝ d with an axis-aligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm. [ABSTRACT FROM AUTHOR]

Given an n-element point set in ℝ d, the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam( η) of η’s boundary. In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup ( S,+) is idempotent if x+ x= x for all x∈ S, and it is integral if for all k≥2, the k-fold sum x+ ⋅⋅⋅+ x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least $\varOmega(1/{\varepsilon }^{d-2\sqrt{d}})$ . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ ε d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ ε)( d−1)/2log (1/ ε)) time using O( n/ ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ ε)( d−1)/2). This bound is in the decision-tree model and holds irrespective of space. [ABSTRACT FROM AUTHOR]