In sum of radii clustering, the input consists of a finite set of points in a metric space. The problem asks to place a set of k balls centered at a subset of the points such that every point is covered by some ball, and the objective is to minimize the sum of radii of these balls. In the capacitated version of the problem, we want to assign each point to a ball containing it, such that no ball is assigned more than U points, where U denotes the capacity of the points. While constant approximations are known for the uncapacitated version of the problem, there is no work on the capacitated version. We make progress on this problem by obtaining a constant approximation using a Fixed Parameter Tractable (FPT) algorithm. In particular, the running time of the algorithm is of the form 2^O(k²) ⋅ n^O(1). As a warm-up for this result, we also give a constant approximation for the uncapacitated sum of radii clustering problem with matroid constraints, thus obtaining the first FPT approximation for this problem.

In this paper, we consider the colorful k-center problem, which is a generalization of the well-known k-center problem. Here, we are given red and blue points in a metric space, and a coverage requirement for each color. The goal is to find the smallest radius rho, such that with k balls of radius rho, the desired number of points of each color can be covered. We obtain a constant approximation for this problem in the Euclidean plane. We obtain this result by combining a "pseudo-approximation" algorithm that works in any metric space, and an approximation algorithm that works for a special class of instances in the plane. The latter algorithm uses a novel connection to a certain matching problem in graphs.

Given a set of obstacles and two points, is there a path between the two points that does not cross more than $k$ different obstacles? This is a fundamental problem that has undergone a tremendous amount of work. It is known to be NP-hard, even when the obstacles are very simple geometric shapes (e.g., unit-length line segments). The problem can be generalized into the following graph problem: Given a planar graph $G$ whose vertices are colored by color sets, two designated vertices $s, t \in V(G)$, and $k \in \mathbb{N}$, is there an $s$-$t$ path in $G$ that uses at most $k$ colors? If each obstacle is connected, the resulting graph satisfies the color-connectivity property, namely that each color induces a connected subgraph. We study the complexity and design algorithms for the above graph problem with an eye on its geometric applications. We prove that without the color-connectivity property, the problem is W[SAT]-hard parameterized by $k$. A corollary of this result is that, unless W[2] $=$ FPT, the problem cannot be approximated in FPT time to within a factor that is a function of $k$. By describing a generic plane embedding of the graph instances, we show that our hardness results translate to the geometric instances of the problem. We then focus on graphs satisfying the color-connectivity property. By exploiting the planarity of the graph and the connectivity of the colors, we develop topological results to "represent" the valid $s$-$t$ paths containing subsets of colors from any vertex $v$. We employ these results to design an FPT algorithm for the problem parameterized by both $k$ and the treewidth of the graph, and extend this result to obtain an FPT algorithm for the parameterization by both $k$ and the length of the path. The latter result directly implies previous FPT results for various obstacle shapes, such as unit disks and fat regions.

We study a generalization of the Set Cover problem called the Partial Set Cover in the context of geometric set systems. The input to this problem is a set system (X, R), where X is a set of elements and R is a collection of subsets of X, and an integer k <= |X|. Each set in R has a non-negative weight associated with it. The goal is to cover at least k elements of X by using a minimum-weight collection of sets from R. The main result of this article is an LP rounding scheme which shows that the integrality gap of the Partial Set Cover LP is at most a constant times that of the Set Cover LP for a certain projection of the set system (X, R). As a corollary of this result, we get improved approximation guarantees for the Partial Set Cover problem for a large class of geometric set systems.

In this article, we consider the following capacitated covering problem. We are given a set P of n points and a set B of balls from some metric space, and a positive integer U that represents the capacity of each of the balls in B. We would like to compute a subset B' subseteq B of balls and assign each point in P to some ball in B' that contains it, such that the number of points assigned to any ball is at most U. The objective function that we would like to minimize is the cardinality of B'. We consider this problem in arbitrary metric spaces as well as Euclidean spaces of constant dimension. In the metric setting, even the uncapacitated version of the problem is hard to approximate to within a logarithmic factor. In the Euclidean setting, the best known approximation guarantee in dimensions 3 and higher is logarithmic in the number of points. Thus we focus on obtaining "bi-criteria" approximations. In particular, we are allowed to expand the balls in our solution by some factor, but optimal solutions do not have that flexibility. Our main result is that allowing constant factor expansion of the input balls suffices to obtain constant approximations for this problem. In fact, in the Euclidean setting, only (1+epsilon) factor expansion is sufficient for any epsilon > 0, with the approximation factor being a polynomial in 1/epsilon. We obtain these results using a unified scheme for rounding the natural LP relaxation; this scheme may be useful for other capacitated covering problems. We also complement these bi-criteria approximations by obtaining hardness of approximation results that shed light on our understanding of these problems.

Let R, B be a set of n points in R^d, for constant d, where the points of R have integer supplies, points of B have integer demands, and the sum of supply is equal to the sum of demand. Let d(.,.) be a suitable distance function such as the L_p distance. The transportation problem asks to find a map tau : R x B --> N such that sum_{b in B}tau(r,b) = supply(r), sum_{r in R}tau(r,b) = demand(b), and sum_{r in R, b in B} tau(r,b) d(r,b) is minimized. We present three new results for the transportation problem when d(.,.) is any L_p metric: * For any constant epsilon > 0, an O(n^{1+epsilon}) expected time randomized algorithm that returns a transportation map with expected cost O(log^2(1/epsilon)) times the optimal cost. * For any epsilon > 0, a (1+epsilon)-approximation in O(n^{3/2}epsilon^{-d}polylog(U)polylog(n)) time, where U is the maximum supply or demand of any point. * An exact strongly polynomial O(n^2 polylog n) time algorithm, for d = 2.

Clustering problems often arise in fields like data mining and machine learning. Clustering usually refers to the task of partitioning a collection of objects into groups with similar elements, with respect to a similarity (or dissimilarity) measure. Among the clustering problems, k-means clustering in particular has received much attention from researchers. Despite the fact that k-means is a well studied problem, its status in the plane is still open. In particular, it is unknown whether it admits a PTAS in the plane. The best known approximation bound achievable in polynomial time is 9+epsilon. In this paper, we consider the following variant of k-means. Given a set C of points in R^d and a real f > 0, find a finite set F of points in R^d that minimizes the quantity f*|F|+sum_{p in C} min_{q in F} {||p-q||}^2. For any fixed dimension d, we design a PTAS for this problem that is based on local search. We also give a "bi-criterion" local search algorithm for k-means which uses (1+epsilon)k centers and yields a solution whose cost is at most (1+epsilon) times the cost of an optimal k-means solution. The algorithm runs in polynomial time for any fixed dimension. The contribution of this paper is two-fold. On the one hand, we are able to handle the square of distances in an elegant manner, obtaining a near-optimal approximation bound. This leads us towards a better understanding of the k-means problem. On the other hand, our analysis of local search might also be useful for other geometric problems. This is important considering that little is known about the local search method for geometric approximation.

In this paper we consider two metric covering/clustering problems - Minimum Cost Covering Problem (MCC) and k-clustering. In the MCC problem, we are given two point sets X (clients) and Y (servers), and a metric on X cup Y. We would like to cover the clients by balls centered at the servers. The objective function to minimize is the sum of the alpha-th power of the radii of the balls. Here alpha geq 1 is a parameter of the problem (but not of a problem instance). MCC is closely related to the k-clustering problem. The main difference between k-clustering and MCC is that in k-clustering one needs to select k balls to cover the clients. For any eps > 0, we describe quasi-polynomial time (1 + eps) approximation algorithms for both of the problems. However, in case of k-clustering the algorithm uses (1 + eps)k balls. Prior to our work, a 3^alpha and a c^alpha approximation were achieved by polynomial-time algorithms for MCC and k-clustering, respectively, where c > 1 is an absolute constant. These two problems are thus interesting examples of metric covering/clustering problems that admit (1 + eps)-approximation (using (1 + eps)k balls in case of k-clustering), if one is willing to settle for quasi-polynomial time. In contrast, for the variant of MCC where alpha is part of the input, we show under standard assumptions that no polynomial time algorithm can achieve an approximation factor better than O(log |X|) for alpha geq log |X|.

Recently, Adamaszek and Wiese [1, 2] presented a quasi-polynomial time approximation scheme (QPTAS) for the problem of computing a maximum weight independent set for certain families of planar objects. This major advance on the problem was based on their proof that a certain type of separator exists for any independent set. Subsequently, Har-Peled [22] simplified and generalized their result. Mustafa et al. [36] also described a simplification, and somewhat surprisingly, showed that QPTAS's can be obtained for certain, albeit special, type of covering problems. Building on these developments, we revisit two NP-hard geometric partitioning problems – convex decomposition and surface approximation. Partitioning problems combine the features of packing and covering. In particular, since the optimal solution does form a packing, the separator theorems are potentially applicable. Nevertheless, the two partitioning problems we study bring up additional difficulties that are worth examining in the context of the wider applicability of the separator methodology. We show how these issues can be handled in presenting quasi-polynomial time algorithms for these two problems with improved approximation guarantees.

Motivated by the recent research on diversity-aware search, we investigate the k-diverse near neighbor reporting problem. The problem is defined as follows: given a query point q, report the maximum diversity set S of k points in the ball of radius r around q. The diversity of a set S is measured by the minimum distance between any pair of points in $S$ (the higher, the better). We present two approximation algorithms for the case where the points live in a d-dimensional Hamming space. Our algorithms guarantee query times that are sub-linear in n and only polynomial in the diversity parameter k, as well as the dimension d. For low values of k, our algorithms achieve sub-linear query times even if the number of points within distance r from a query $q$ is linear in $n$. To the best of our knowledge, these are the first known algorithms of this type that offer provable guarantees.

We consider variants of the following multi-covering problem with disks. We are given two point sets Y (servers) and X (clients) in the plane, and a coverage function κ :X -> N. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client x ∈ X be covered by at least κ(x) of the server disks. The objective function we wish to minimize is the sum of the areas of the disks. We present a polynomial time algorithm for this problem achieving an O(1) approximation.

In this article, we study shape fitting problems, epsilon-coresets, and total sensitivity. We focus on the (j,k)-projective clustering problems, including k-median/k-means, k-line clustering, j-subspace approximation, and the integer (j,k)-projective clustering problem. We derive upper bounds of total sensitivities for these problems, and obtain epsilon-coresets using these upper bounds. Using a dimension-reduction type argument, we are able to greatly simplify earlier results on total sensitivity for the k-median/k-means clustering problems, and obtain positively-weighted epsilon-coresets for several variants of the (j,k)-projective clustering problem. We also extend an earlier result on epsilon-coresets for the integer (j,k)-projective clustering problem in fixed dimension to the case of high dimension.

We consider the problem of projective clustering in Euclidean spaces of non-fixed dimension. Here, we are given a set P of n points in ℝm and integers j ≥ 1, k ≥ 0, and the goal is to find j k-subspaces so that the sum of the distances of each point in P to the nearest subspace is minimized. Observe that this is a shape fitting problem where we wish to find the best fit in the L1 sense. Here we will treat the number j of subspaces we want to fit and the dimension k of each of them as constants. We consider instances of projective clustering where the point coordinates are integers of magnitude polynomial in m and n. Our main result is a randomized algorithm that for any ε > 0 runs in time O(mn polylog(mn)) and outputs a solution that with high probability is within (1 + ε) of the optimal solution. To obtain this result, we show that the fixed dimensional version of the above projective clustering problem has a small coreset. We do that by observing that in a fairly general sense, shape fitting problems that have small coresets in the L∞ setting also have small coresets in the L1 setting, and then exploiting an existing construction for the L∞ setting. This observation seems to be quite useful for other shape fitting problems as well, as we demonstrate by constructing the first “regular” coreset for the circle fitting problem in the plane.

Let P be a set of n points in the plane. Consider the problem of finding k disks, each centered at a point in P, whose union covers P with the objective of minimizing the sum of the radii of the disks. We present an exact algorithm for this well-studied problem with polynomial running time, under the assumption that two candidate solutions can be compared efficiently. The algorithm generalizes in a straightforward manner to any fixed dimension and to some other related problems.

Given a graph G = ( V, E ) and positive integral vertex weights w : V → N , the max-coloring problem seeks to find a proper vertex coloring of G whose color classes C 1 , C 2 , …, C k , minimize ∑ i =1 k max v ∈ C i w ( v ). This problem, restricted to interval graphs, arises whenever there is a need to design dedicated memory managers that provide better performance than the general-purpose memory management of the operating system. Though this problem seems similar to the dynamic storage allocation problem, there are fundamental differences. We make a connection between max-coloring and online graph coloring and use this to devise a simple 2-approximation algorithm for max-coloring on interval graphs. We also show that a simple first-fit strategy, that is a natural choice for this problem, yields an 8-approximation algorithm. We show this result by proving that the first-fit algorithm for online coloring an interval graph G uses no more than 8 ċ χ( G ) colors, significantly improving the bound of 26 ċ χ( G ) by Kierstead and Qin [1995]. We also show that the max-coloring problem is NP-hard. The problem of online coloring of intervals with bandwidths is a simultaneous generalization of online interval coloring and online bin packing. The input is a set I of intervals, each interval i ∈ I having an associated bandwidth b ( i ) ∈ (0, 1]. We seek an online algorithm that produces a coloring of the intervals such that for any color c and any real r , the sum of the bandwidths of intervals containing r and colored c is at most 1. Motivated by resource allocation problems, Adamy and Erlebach [2003] consider this problem and present an algorithm that uses at most 195 times the number of colors used by an optimal offline algorithm. Using the new analysis of first-fit coloring of interval graphs, we show that the Adamy-Erlebach algorithm is 35-competitive. Finally, we generalize the Adamy-Erlebach algorithm to a class of algorithms and show that a different instance from this class is 30-competitive.

There has been much progress on geometric set cover problems, but most known techniques only apply to the unweighted setting. For the weighted setting, very few results are known with approximation guarantees better than that for the combinatorial set cover problem. In this article, we employ the idea of quasi-uniform sampling to obtain improved approximation guarantees in the weighted setting for a large class of problems for which such guarantees were known in the unweighted case. As a consequence of this sampling method, we obtain new results on the fractional set cover packing problem.

We consider the following combinatorial problem: given a set of n objects (for example, disks in the plane, triangles), and an integer L ≥ 1, what is the size of the smallest subset of these n objects that covers all points that are in at least L of the objects? This is the classic question about the size of an L/n-net for these objects. It is well known that for fairly general classes of geometric objects the size of an L/n-net is O(n/L log n/L). There are some instances where this general bound can be improved, and this improvement is usually due to bounds on the combinatorial complexity (size) of the boundary of the union of these objects. Thus, the boundary of the union of m disks has size O(m), and this translates to an O(n/L) bound on the size of an L/n-net for disks. For m fat triangles, the size of the union boundary is O(m log log m), and this yields L/n-nets of size O(n/L log log n/L). Improved nets directly translate into an upper bound on the ratio between the optimal integral solution and the optimal fractional solution for the corresponding geometric set cover problem. Thus, for covering k points by disks, this ratio is O(1); and for covering k points by fat triangles, this ratio is O(log log k). This connection to approximation algorithms for geometric set cover is a major motivation for attempting to improve bounds on nets. Our main result is an argument that in some cases yields nets that are smaller than those previously obtained from the size of the union boundary. Thus for fat triangles, for instance, we obtain nets of size O(n/L log log log n). We use this to obtain a randomized polynomial time algorithm that gives an O(log log log k)-approximation for the problem of covering k points by the smallest subset of a given set of triangles.

We show that a k-fold covering using translates of an arbitrary convex polygon can be decomposed into Omega(k) covers (using an efficient algorithm). We generalize this result to obtain a constant factor approximation to the sensor cover problem where the ranges of the sensors are translates of a given convex polygon. The crucial ingredient in this generalization is a constant factor approximation algorithm for a one-dimensional version of the sensor cover problem, called the Restricted Strip Cover (RSC) problem, where sensors are intervals of possibly different lengths. Our algorithm for RSC improves on the previous O(log log log n) approximation.

We give a randomized bi-criteria algorithm for the problem of finding a k-dimensional subspace that minimizesthe Lp-error for given points, i.e., p-th root of the sum of p-th powers of distances to given points,for any p ≥ 1. Our algorithm runs in time Õ (mn · pk3 (k/ε)2p) andproduces a subset of size Õ (pk2 (k/ε)2p) from the given points such that, withhigh probability, the span of these points gives a (1+ε)-approximation to the optimal k-dimensionalsubspace. We also show a dimension reduction type of result for this problem where we can efficiently find asubset of size Õ (pk2(p+1) + (k/ε)p+2) such that, with high probability, theirspan contains a k-dimensional subspace that gives (1+ε)-approximation to the optimum. We prove similarresults for the corresponding projective clustering problem where we need to find multiple k-dimensional subspaces.

We consider the problem of computing the outer‐radii of point sets. In this problem, we are given integers $n, d$, and k, where $k \le d$, and a set P of n points in $\Re^d$. The goal is to compute the outer k‐radius of P, denoted by ${\cal R}_k(P)$, which is the minimum over all $(d-k)$‐dimensional flats F of $\max_{p \in P} d(p,F)$, where $d(p,F)$ is the Euclidean distance between the point p and flat F. Computing the radii of point sets is a fundamental problem in computational convexity with many significant applications. The problem admits a polynomial time algorithm when the dimension d is constant [U. Faigle, W. Kern, and M. Streng, Math. Program., 73 (1996), pp. 1–5]. Here we are interested in the general case in which the dimension d is not fixed and can be as large as n, where the problem becomes NP‐hard even for $k=1$. It is known that $R_k(P)$ can be approximated in polynomial time by a factor of $(1 + \varepsilon)$ for any $\varepsilon > 0$ when $d - k$ is a fixed constant [M. Bădoiu, S. Har‐Peled, and P. Indyk, in Proceedings of the ACM Symposium on the Theory of Computing, 2002; S. Har‐Peled and K. Varadarajan, in Proceedings of the ACM Symposium on Computing Geometry, 2002]. A polynomial time algorithm that guarantees a factor of $O(\sqrt{\log n})$ approximation for $R_1(P)$, the width of the point set P, is implied by the results of Nemirovski, Roos, and Terlaky [Math. Program., 86 (1999), pp. 463–473] and Nesterov [Handbook of Semidefinite Programming Theory, Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000]. In this paper, we show that $R_k(P)$ can be approximated by a ratio of $O(\sqrt{\log n})$ for any $1 \leq k \leq d$, thus matching the previously best known ratio for approximating the special case $R_1 (P)$, the width of point set P. Our algorithm is based on semidefinite programming relaxation with a new mixed deterministic and randomized rounding procedure. We also prove an inapproximability result that gives evidence that our approximation algorithm is doing well for a large range of k. We show that there exists a constant $\delta > 0$ such that the following holds for any $0 < \eps < 1$: there is no polynomial time algorithm that approximates $R_k(P)$ within $(\log n)^{\delta}$ for all k such that $k \leq d - d^{\varepsilon}$ unless NP $\subseteq$ DTIME $[2^{(\log m)^{O(1)}}]$. Our inapproximability result for $R_k(P)$ extends a previously known hardness result of Brieden [Discrete Comput. Geom., 28 (2002), pp. 201–209] and is proved by modifying Brieden’s construction using basic ideas from probabilistically checkable proofs (PCP) theory.

Given a collection S of subsets of some set U, and M ⊂ U, the set cover problem is to find the smallest subcollection C ⊂ S such that M is a subset of the union of the sets in C. While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where usually U = Rd. Combining previously known techniques [3, 4], we show that polynomial time approximation algorithms with provable performance exist, under a certain general condition: that for a random subset R ⊂ S and function f(), there is a decomposition of the complement U ∖ ∪Y ∈ R Y into an expected f(|R|) regions, each region of a particular simple form. Under this condition, a cover of size O(f(|C|)) can be found in polynomial time. Using this result, and combinatorial geometry results implying bounding functions f(c) that are nearly linear, we obtain o(log c) approximation algorithms for covering by fat triangles, by pseudodisks, by a family of fat objects, and others. Similarly, constant-factor approximations follow for similar-sized fat triangles and fat objects, and for fat wedges. With more work, we obtain constant-factor approximation algorithms for covering by unit cubes in R3, and for guarding an x-monotone polygonal chain.

We consider the problem of computing market equilibria and show three results. (i) For exchange economies satisfying weak gross substitutability we analyze a simple discrete version of tâtonnement, and prove that it converges to an approximate equilibrium in polynomial time. This is the first polynomial-time approximation scheme based on a simple tâtonnement process. It was only recently shown, using vastly more sophisticated techniques, that an approximate equilibrium for this class of economies is computable in polynomial time. (ii) For Fisher’s model, we extend the frontier of tractability by developing a polynomial-time algorithm that applies well beyond the homothetic case and the gross substitutes case. (iii) For production economies, we obtain the first polynomial-time algorithms for computing an approximate equilibrium when the consumers ’ side of the economy satisfies weak gross substitutability and the producers’ side is restricted to positive production.

In the Euclidean bipartite matching problem, we are given a set R of "red" points and a set B of "blue" points in ℝ3 where |R| = |B| = n, and we want to pair up each red point with a distinct blue point so that the sum of distances between the paired points is minimized. We present an approximation algorithm that given any parameter 0 < ε < 1 runs in O(n1+ε) expected time and returns a matching whose expected cost is within a multiplicative factor O(log (1/ε)) of the optimal. The dimension d is considered to be a fixed constant.

The notion of ε-kernel was introduced by Agarwal et al. to set up a unified framework for computing various extent measures of a point set p approximately. Roughly speaking, a subset Q ⊆ P is an ε-kernel of P if for every slab W containing Q, the expanded slab (1+ε)W contains P. They illustrated the significance of an ε-kernel by showing that it yields approximation algorithms for a wide range of problems.We present a simpler and more practical algorithm for computing the ε-kernel of a set P of points in ℝ3. We demonstrate the practicality of our algorithm by showing its empirical performance on various inputs. We then describe an incremental algorithm for fitting various shapes and use the ideas of our algorithm for computing ε-kernels to analyze the performance of this algorithm. We illustrate the versatility and practicality of this technique by implementing approximation algorithms for minimum enclosing cylinder, minimum-volume bounding box, and minimum-width annulus. Finally, we show that ε-kernels can be effectively used to expedite the algorithms for maintaining extents of moving points.

We present a general technique for approximating various descriptors of the extent of a set P of n points in R d when the dimension d is an arbitrary fixed constant. For a given extent measure μ and a parameter ε > 0, it computes in time O ( n + 1/ε O (1) ) a subset Q ⊆ P of size 1/ε O (1) , with the property that (1 − ε)μ( P ) ≤ μ( Q ) ≤ μ( P ). The specific applications of our technique include ε-approximation algorithms for (i) computing diameter, width, and smallest bounding box, ball, and cylinder of P , (ii) maintaining all the previous measures for a set of moving points, and (iii) fitting spheres and cylinders through a point set P . Our algorithms are considerably simpler, and faster in many cases, than previously known algorithms.

Let P be a set of n points in Rd. The radius of a k-dimensional flat F with respect to P, denoted by RD(F,P), is defined to be maxp ? P dist(F,p), where dist(F,p) denotes the Euclidean distance between p and its projection onto F. The k-flat radius of P, which we denote by Rkopt(P), is the minimum, over all k-dimensional flats F, of RD(F,P). We consider the problem of computing Rkopt(P) for a given set of points P. We are interested in the high-dimensional case where d is a part of the input and not a constant. This problem is NP-hard even for k = 1. We present an algorithm that, given P and a parameter 0 < e = 1, returns a k-flat F such that RD(F,P) = (1 + e) Rkopt(P). The algorithm runs in O(nd Ce,k) time, where Ce,k is a constant that depends only on e and k. Thus the algorithm runs in time linear in the size of the point set and is a substantial improvement over previous known algorithms, whose running time is of the order of d nO(k/ec), where c is an appropriate constant.

(MATH) Let P be a set of n points in $\Red, and for any integer 0 ≤ k ≤ d--1, let $\RDk(P) denote the minimum over all k-flats $\FLAT$ of maxpεP Dist(p,\FLAT). We present an algorithm that computes, for any 0 < ε < 1, a k-flat that is within a distance of (1 + $egr;) \RDk(P) from each point of P. The running time of the algorithm is dnO(k/ε5log(1/ε)). The crucial step in obtaining this algorithm is a structural result that says that there is a near-optimal flat that lies in an affine subspace spanned by a small subset of points in P. The size of this "core-set" depends on k and ε but is independent of the dimension.This approach also extends to the case where we want to find a k-flat that is close to a prescribed fraction of the entire point set, and to the case where we want to find j flats, each of dimension k, that are close to the point set. No efficient approximation schemes were known for these problems in high-dimensions, when k>1 or j>1.

Let P be a set of n points in /spl Ropf//sup d/. For any 1/spl les/k/spl les/d, the outer k-radius of P, denoted by R/sub k/(P), is the minimum, over all (d-k) -dimensional fiats F, of max/sub p/spl isin/P/ d(p, F), where d(p, F) is the Euclidean distance between the point p and fiat F. We consider the scenario when the dimension d is not fixed and can be as large as n. Computing the various radii of point sets is a fundamental problem in computational convexity with many applications. The main result of this paper is a randomized polynomial time algorithm that approximates Rk (P) to within a factor of O/spl radic/(log n/spl middot/log d) for any 1/spl les/k/spl les/d. This algorithm is obtained using techniques from semidefinite programming and dimension reduction. Previously, good approximation algorithms were known only for the case k=1 and for the case when k=d-c for any constant c; there are polynomial time algorithms that approximate Rk(P) to within a factor of (1+/spl epsi/), for any /spl epsi/>0, when d-k is any fixed constant. On the other hand, some results from the mathematical programming community on approximating certain kinds of quadratic programs imply an O/spl radic/(log n) approximation for R/sub 1/ (P), the width of the point set P. We also prove an inapproximability result for computing Rk (P), which easily yields the conclusion that our approximation algorithm performs quite well for a large range of values of k. Our inapproximability result for Rk (P) improves the previous known hardness result of Brieden, and is proved by improving the parameters in Brieden's construction using basic ideas from PCP theory.

We show that the maximum number of geometric permutations of a set of $n$ pairwise-disjoint convex and fat objects in $\reals^d$ is $O(n^{d-1})$. This generalizes the bound of $\Theta (n^{d-1})$ obtained by Smorodinsky et al. \cite{ssm98} on the number of geometric permutations of $n$ pairwise-disjoint balls.

Shape fitting is a fundamental optimization problem in computer science. The authors present a general and unified technique for solving a certain family of such problems. Given a point set P in R/sup d/, this technique can be used to /spl epsi/-approximate: (i) the min-width annulus and shell that contains P, (ii) minimum width cylindrical shell containing P, (iii) diameter, width, minimum volume bounding box of P, and (iv) all the previous measures for the case the points are moving. The running time of the resulting algorithms is O(n + 1//spl epsi//sup c/), where c is a constant that depends on the problem at hand. Our new general technique enables us to solve those problems without resorting to a careful and painful case by case analysis, as was previously done for those problems. Furthermore, for several of those problems our results are considerably simpler and faster than what was previously known. In particular, for the minimum width cylindrical shell problem, our solution is the first algorithm whose running time is subquadratic in n. (In fact we get running time linear in n.).

It has been known for a long time now that the problem of counting the number of perfect matchings in a planar graph is in NC.This result is based on the notion of a pfaffian orientation of a graph.(Recently, Galluccio and Loebl [7] gave a P-time algorithm for the case of graphs of small genus.)However, it is not known if the corresponding search problem, that of finding one perfect matching in a planar graph, is in NC.This situation is intriguing as it seems to contradict our intuition that search should be easier than counting.For the case of planar bipartite graphs, Miller and Naor [22] showed that a perfect matching can indeed be found using an NC algorithm.We present a very different NG-algorithm for this problem.Unlike the Miller-Naor algorithm, our approach directly uses the fact that counting is in NC, and it also generalizes to the problem of finding a perfect matching in a bipartite graph of small (O(log n)) genus.It also rekindles the hope for an NC-algorithm to find a perfect matching in a non-bipartite planar graph.Along the way, we modify the algorithm of Gallucio and Loebl [7] to show that counting the number of perfect matchings in graphs of small genus is in NC.

We present an approximation algorithm that, given the boundary P of a simple, nonconvex polyhedron in ${\mathbb R}^3$ and two points s and t on P, constructs a path on P between s and t whose length is at most ${7(1+{\varepsilon})} d P (s,t), where d P (s,t) is the length of the shortest path between s and t on P, and ${\varepsilon} > 0$ is an arbitrarily small positive constant. The algorithm runs in O(n 5/3 log 5/3 n ) time, where n is the number of vertices in P. We also present a slightly faster algorithm that runs in O(n 8/5 log 8/5 n ) time and returns a path whose length is at most ${15(1+{\varepsilon})} d_{P}(s,t)$.

Given a set V of 2n points in the plane, the min-cost perfect matching problem is to pair up the points (into n pairs) so that the sum of the Euclidean distances between the paired points is minimized. We present an O(n/sup 3/2/log/sup 5/ n)-time algorithm for computing a min-cost perfect matching in the plane, which is an improvement over the previous best algorithm of Vaidya [1989) by nearly a factor of n. Vaidya's algorithm is an implementation of the algorithm of Edmonds (1965), which runs in n phases, and computes a matching with i edges at the end of the i-th phase. Vaidya shows that geometry can be exploited to implement a single phase in roughly O(n/sup 3/2/) time, thus obtaining an O(n/sup 5/2/log/sup 4/ n)-time algorithm. We improve upon this in two major ways. First, we develop a variant of Edmonds algorithm that uses geometric divide-and-conquer, so that in the conquer step we need only O(/spl radic/n) phases. Second, we show that a single phase can be implemented in O(n log/sup 5/ n) time.

We present an approximation algorithm that, given the boundary P of a simple, nonconvex polyhedron in R/sup 3/, and two points s and t on P, constructs a path on P between s and t whose length is at most 7(1+/spl epsi/)d/sub P/(s,t), where d/sub P/(s,t) is the length of the shortest path between s and t on P, and /spl epsi/>0 is an arbitrarily small positive constant. The algorithm runs in O(n/sup 5/3/ log/sup 5/3/ n) time, where n is the number of vertices in P. We also present a slightly faster algorithm that runs in O(n/sup 8/5/ log/sup 8/5/ n) time and returns a path whose length is at most 15(1+/spl epsi/)d/sub P/(s,t).

Given a convex polytope P with n faces in ℝ 3 , points ∈ ∂P, and a parameter 0 < ϵ ≤ 1, we present an algorithm that constructs a path on ∂P from s to t whose length is at most (1 + ϵ) d p (s, t) , where d p (s, t) is the length of the shortest path between s and t on ∂P. The algorithm runs in O(n log 1/ϵ + 1/ϵ 3 ) time, and is relatively simple. The running time is O(n + 1/ϵ 3 ) if we only want the approximate shortest path distance and not the path itself. We also present an extension of the algorithm that computes approximate shortest path distances from a given source point on ∂P to all vertices of P .

We present an approximation algorithm that, given a convex polytope P with n faces in lR3, points s, t c 8P, and a parameter O < & <1, constructs a path on t3P from s to t whose length is at most (1 +E)dP(S, t), where dp (s, t) is the length of the shortest path between s and t on 8P.The algorithm runs intime. and is relatively simple to implement.We also present an extension of the algorithm that computes approximate shortest paths from a given source point on 8P to all vertices of P.

We consider the problem of approximating a monotone polygonal chain C by another polygonal chain C' whose vertices are constrained to be a subset of the set of vertices of C. The goal is to minimize the number of vertices needed in the approximation C'.We use the uniform metric as the error criterion for the approximation.We consider two problems.(1) Given e ?O, find an approximation, among all approximations whose error is at most e. that has the smallest number of vertices.We give an 0(n4f3+6 )- time algorithm to solve this problem; throughout this paper, d > 0 is an arbitrarily small constant, and the constant of proportionality hidden in the big-Oh notation depends on 6. (2) Given an integer k, find an approximation with at most k vertices whose error is the smallest among all approximations with at most k vertices.We give a simple randomized algorithm, with expected running time 0(n413+d), to solve this problem.We also present a deterministic version of the algorithm that has the same asymptotic time complexity.Algorithms with close to linear running times are known for the variants of this problem which do not restrict the vertices of the approximation C' to be a subset of the set of vertices of C. Ours is the first non-trivial instance of a subquadratic-time algorithm for the restricted case.