Fitting enclosing cylinders to data in R n

A simple iterative algorithm is given for finding a stationary point of the (non-convex) problem of finding the smallest enclosing (n–d)-cylinder to discrete data in R ⁿ , that is a cylinder whose axis is a d-dimensional linear manifold. An important special case is the problem of finding the smallest enclosing (usual) cylinder, when n=3 and d=1. The method is based on the solution of a sequence of second order cone programming problems, which can be efficiently solved by interior point methods and for which good software packages are available.     

Efficient Algorithms for the Smallest Enclosing Ball Problem

Consider the problem of computing the smallest enclosing ball of a set of m balls in ⁿ. Existing algorithms are known to be inefficient when n > 30. In this paper we develop two algorithms that are particularly suitable for problems where n is large. The first algorithm is based on log-exponential aggregation of the maximum function and reduces the problem into an unconstrained convex program. The second algorithm is based on a second-order cone programming formulation, with special structures taken into consideration. Our computational experiments show that both methods are efficient for large problems, with the product mn on the order of 10⁷. Using the first algorithm, we are able to solve problems with n = 100 and m = 512,000 in about 1 hour.His work was supported by Australian Research Council.Research supported in part by the Singapore-MIT Alliance.     

The Discrete 2-Center Problem

We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P , whose union covers P . Our algorithm runs in time O(n ^4/3 log ⁵ n) . Received July 18, 1997, and in revised form March 17, 1998.     

Largest bounding box,smallest diameter,and related problems on imprecise points

Imprecision of input data is one of the main obstacles that prevent geometric algorithms from being used in practice. We model an imprecise point by a region in which the point must lie. Given a set of imprecise points, we study computing the largest and smallest possible values of various basic geometric measures on point sets, such as the diameter, width, closest pair, smallest enclosing circle, and smallest enclosing bounding box. We give efficient algorithms for most of these problems, and identify the hardness of others.     

Simple proofs of occupancy tail bounds

We give a simple proof of an occupancy tail bound in the balls and bins experiment using the method of bounded differences in expected form. We also indicate how a short, calculation-free proof of another occupancy tail bound follows from an extension of the standard Chernoff–Hoeffding bounds to variables that satisfy some general notions of negative dependence. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 119–123 (1997)     

Dynamic Coresets

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. This work has been supported by NSERC. A preliminary version of this paper has appeared in Proc. 24th ACM Sympos Comput. Geom., 2008.     

On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension

We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic algorithm. The constant of proportionality isd^O(d), which is better than those for previously known algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems, e.g., computing the minimum-volume ellipsoid enclosing a set ofnpoints and finding the maximum volume ellipsoid in the intersection ofnhalfspaces.     

On the graphs with given diameter,number of vertices,and local diversity of balls

In connection with the problem of characterizing the diversity vectors of balls in ordinary connected graphs, we study the n-vertex graphs with diameter d and local t-diversity of balls; i.e., the graphs that have n different balls of radius i for all i ≤ t. For these graphs, a lower bound is available for the number of vertices defined by d and t. In this work, we explicitly up to an isomorphism describe all graphs with diameter d and the local t-diversity of balls (full diversity of balls) that have the smallest order. Moreover, the diversity vector of balls is calculated for each of these graphs.     

Minimal Time Functions and the Smallest Intersecting Ball Problem with Unbounded Dynamics

The smallest enclosing circle problem introduced in the nineteenth century by Sylvester asks for the circle of smallest radius enclosing a given set of finite points in the plane. An extension of this problem, called the smallest intersecting ball problem, was also considered recently: given a finite number of nonempty closed subsets of a normed space, find a ball with the smallest radius that intersects all of the sets. In this paper, we initiate the study of minimal time functions generated by unbounded dynamics and discuss their applications to further extensions of the smallest enclosing circle problem. This approach continues our effort in applying convex and nonsmooth analysis to the well-established field of facility location.     

Volumetric bounds for intersections of congruent balls in Euclidean spaces

We investigate the intersections of balls of radius r, called r-ball bodies, in Euclidean d-space. An r-lense (resp., r-spindle) is the intersection of two balls of radius r (resp., balls of radius r containing a given pair of points). We prove that among r-ball bodies of a given volume, the r-lense (resp., r-spindle) has the smallest inradius (resp., largest circumradius). In general, we upper (resp., lower) bound the intrinsic volumes of r-ball bodies of a given inradius (resp., circumradius). This complements and extends some earlier results on volumetric estimates for r-ball bodies.

     

Enclosing a Set of Objects by Two Minimum Area Rectangles

In this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose anO(nα(n)log n) worst-case time algorithm, where α( ) is the inverse Ackermann's function, for finding, given a setMof points, segments and polygons defined bynvertices, a pair of axis-parallel rectangles (s, t) such thats∪tencloses all objects inMand area(s)+area(t) is minimum. The algorithm works inO(nα(n) log log n) worst-case space. Moreover, we prove an Ω(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case timeO(n log n), using worst-case spaceO(n log log n).     

On geometric optimization with few violated constraints

We investigate the problem of finding the best solution satisfying all butk of the given constraints, for an abstract class of optimization problems introduced by Sharir and Welzl—the so-calledLP-type problems. We give a general algorithm and discuss its efficient implementations for specific geometric problems. For instance for the problem of computing the smallest circle enclosing all butk of the givenn points in the plane, we obtain anO(n logn+k ³ n ^ε) algorithm; this improves previous results fork small compared withn but moderately growing. We also establish some results concerning general properties ofLP-type problems. This research was supported in part by Charles University Grant No. 351 and Czech Republic Grant GAČR 201/93/2167. Part of this research was performed while the author was visting the Computer Science Institute, Free University Berlin, and it was supported by the German-Israeli Foundation of Scientific Research and Development (G.I.F.), and part while visiting the Max-Planck Institute for Computer Science in Saarbrücken.     

On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids

Given A?{a¹,…,a^m}⊂R^d whose affine hull is R^d, we study the problems of computing an approximate rounding of the convex hull of A and an approximation to the minimum-volume enclosing ellipsoid of A. In the case of centrally symmetric sets, we first establish that Khachiyan's barycentric coordinate descent (BCD) method is exactly the polar of the deepest cut ellipsoid method using two-sided symmetric cuts. This observation gives further insight into the efficient implementation of the BCD method. We then propose a variant algorithm which computes an approximate rounding of the convex hull of A, and which can also be used to compute an approximation to the minimum-volume enclosing ellipsoid of A. Our algorithm is a modification of the algorithm of Kumar and Y?ld?r?m, which combines Khachiyan's BCD method with a simple initialization scheme to achieve a slightly improved polynomial complexity result, and which returns a small “core set.” We establish that our algorithm computes an approximate solution to the dual optimization formulation of the minimum-volume enclosing ellipsoid problem that satisfies a more complete set of approximate optimality conditions than either of the two previous algorithms. Furthermore, this added benefit is achieved without any increase in the improved asymptotic complexity bound of the algorithm of Kumar and Y?ld?r?m or any increase in the bound on the size of the computed core set. In addition, the “dropping idea” used in our algorithm has the potential of computing smaller core sets in practice. We also discuss several possible variants of this dropping technique.     

A Near-Linear Algorithm for the Planar 2-Center Problem

We present an -time algorithm for computing the 2-center of a set S of n points in the plane (that is, a pair of congruent disks of smallest radius whose union covers S), improving the previous -time algorithm of [10]. Received May 2, 1995, and in revised form July {8, 1995}.     

On the quality of algorithms based on spline interpolation

The qualityq of a numerical algorithm using some specified information is the ratio of its error to the smallest possible error of an algorithm based on the same information. We use as information function values at equidistant points, periodicity and a bound for therth derivative. We show thatq is rather small, if the algorithm is based on spline interpolation.     

On Four-Connecting a Triconnected Graph

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n · α(m, n) + m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and α(m, n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k − 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.     

A fast algorithm for computing the smallest eigenvalue of a symmetric positive‐definite Toeplitz matrix

Recent progress in signal processing and estimation has generated considerable interest in the problem of computing the smallest eigenvalue of a symmetric positive‐definite (SPD) Toeplitz matrix. An algorithm for computing upper and lower bounds to the smallest eigenvalue of a SPD Toeplitz matrix has been recently derived (Linear Algebra Appl. 2007; DOI: 10.1016/j.laa.2007.05.008 ). The algorithm relies on the computation of the R factor of the QR factorization of the Toeplitz matrix and the inverse of R. The simultaneous computation of R and R^?1 is efficiently accomplished by the generalized Schur algorithm. In this paper, exploiting the properties of the latter algorithm, a numerical method to compute the smallest eigenvalue and the corresponding eigenvector of SPD Toeplitz matrices in an accurate way is proposed. Copyright © 2008 John Wiley & Sons, Ltd.     

Finding the Medial Axis of a Simple Polygon in Linear Time

We give a linear-time algorithm for computing the medial axis of a simple polygon P . This answers a long-standing open question—previously, the best deterministic algorithm ran in O(n log n) time. We decompose P into pseudonormal histograms, then influence histograms, then xy monotone histograms. We can compute the medial axes for xy monotone histograms and merge to obtain the medial axis for P . Received May 16, 1997, and in revised form October 30, 1997.     

On the Area Bisectors of a Polygon

We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different partitionings of the vertices of P . We derive an algebraic characterization of area bisectors. We then show that there are simple polygons with n vertices that have Ω(n ² ) combinatorially distinct area bisectors (matching the obvious upper bound), and present an output-sensitive algorithm for computing an explicit representation of all the bisectors of a given polygon. Received September 11, 1997, and in revised form April 8, 1998.     

The Number of Cylindrical Shells

Given a set P of n points in three dimensions, a cylindrical shell (or zone cylinder) is formed by two circular cylinders with the same axis such that all points of P are between the two cylinders. We prove that the number of cylindrical shells enclosing P passing through combinatorially different subsets of P has size (n ³) and O(n ⁴) (the previously known bound was O(n ⁵)). As a consequence, the minimum enclosing shell can be found in O(n ⁴) time.