Optimally Cutting a Surface into a Disk

We consider the problem of cutting a subset of the edges of a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard in general, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n ^O(g+k), where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs a O(log² g)-approximation of the minimum cut graph in O(g ² n log n) time.     

Approximate Shortest Paths and Geodesic Diameter on a Convex Polytope in Three Dimensions

Given a convex polytope P with n edges in ³ , we present a relatively simple algorithm that preprocesses P in O(n) time, such that, given any two points , and a parameter 0 < 1, it computes, in O(log n) /ɛ ^1.5 + 1/ ɛ ³ ) time, a distance Δ _P (s,t) , such that d _P (s,t) Δ _P (s,t) (1+ɛ )d _P (s,t) , where d _P (s,t) is the length of the shortest path between s and t on . The algorithm also produces a polygonal path with O (1/ɛ ^1.5 ) segments that avoids the interior of P and has length Δ _P (s,t) . Our second related result is: Given a convex polytope P with n edges in ³ , and a parameter 0 < 1, we present an O (n + 1/ ɛ ⁵ )-time algorithm that computes two points such that , where is the geodesic diameter of P . Received April 8, 1997, and in revised form August 3, 1997.     

New constructions of SSPDs and their applications

We present a new optimal construction of a semi-separated pair decomposition (i.e., SSPD) for a set of n points in ${\mathbb{R}}^d$. In the new construction each point participates in a few pairs, and it extends easily to spaces with low doubling dimension. This is the first optimal construction with these properties.As an application of the new construction, for a fixed $t>1$, we present a new construction of a t-spanner with $O(n)$ edges and maximum degree $O({\log }^{2}n)$ that has a separator of size $O(n^{1?1/d})$.     

On the Least Median Square Problem

We consider the exact and approximate computational complexity of the multivariate least median-of-squares (LMS) linear regression estimator. The LMS estimator is among the most widely used robust linear statistical estimators. Given a set of n points in and a parameter k, the problem is equivalent to computing the narrowest slab bounded by two parallel hyperplanes that contains k of the points. We present algorithms for the exact and approximate versions of the multivariate LMS problem. We also provide nearly matching lower bounds for these problems. These lower bounds hold under the assumptions that k is Ω(n) and that deciding whether n given points in are affinely non-degenerate requires Ω(n^d) time.     

On the Fermat–Weber center of a convex object

We show that for any convex object Q in the plane, the average distance from the Fermat–Weber center of Q to the points in Q is at least Δ(Q)/7, where Δ(Q) is the diameter of Q, and that there exists a convex object P for which this distance is Δ(P)/6. We use this result to obtain a linear-time approximation scheme for finding an approximate Fermat–Weber center of a convex polygon Q.     

Smaller Coresets for k-Median and k-Means Clustering

In this paper we show that there exists a -coreset for k-median and k-means clustering of n points in which is of size independent of n. In particular, we construct a -coreset of size for k-median clustering, and of size for k-means clustering.