The smallest enclosing ball problem and the smallest intersecting ball problem: existence and uniqueness of solutions

In this paper we study the following problems and their further generalizations: given a finite number of nonempty closed subsets of a normed space, find a ball with the smallest radius that encloses all of the sets, and find a ball with the smallest radius that intersects all of the sets. These problems can be viewed as generalized versions of the smallest enclosing circle problem introduced in the nineteenth century by Sylvester which asks for the circle of smallest radius enclosing a given set of finite points in the plane. We will focus on sufficient conditions for the existence and uniqueness of an optimal solution for each problem, while the study of optimality conditions and numerical implementation will be addressed in our next projects.     

Adaptive and restarting techniques-based algorithms for circular packing problems

In this paper, we study the circular packing problem (CPP) which consists of packing a set of non-identical circles of known radii into the smallest circle with no overlap of any pair of circles. To solve CPP, we propose a three-phase approximate algorithm. During its first phase, the algorithm successively packs the ordered set of circles. It searches for each circle’s “best” position given the positions of the already packed circles where the best position minimizes the radius of the current containing circle. During its second phase, the algorithm tries to reduce the radius of the containing circle by applying (i) an intensified search, based on a reduction search interval, and (ii) a diversified search, based on the application of a number of layout techniques. Finally, during its third phase, the algorithm introduces a restarting procedure that explores the neighborhood of the current solution in search for a better ordering of the circles. The performance of the proposed algorithm is evaluated on several problem instances taken from the literature.     

Solution Methodologies for the Smallest Enclosing Circle Problem

Given a set of circles C = {c ₁, ..., c _n} on the Euclidean plane with centers {(a ₁, b ₁), ..., (a _n, b _n)} and radii {r ₁, ..., r _n}, the smallest enclosing circle (of fixed circles) problem is to find the circle of minimum radius that encloses all circles in C. We survey four known approaches for this problem, including a second order cone reformulation, a subgradient approach, a quadratic programming scheme, and a randomized incremental algorithm. For the last algorithm we also give some implementation details. It turns out the quadratic programming scheme outperforms the other three in our computational experiment.     

A branch-and-bound method for the minimum k−enclosing ball problem

The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of m given points. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of k points to solve this problem. Our method is able to solve the problem exactly in a short amount of time for small and medium sized datasets.     

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.     

The problem of a minimal ball enclosing <Emphasis Type="Italic">k</Emphasis> points

Under study is the problem of finding a ball of minimal radius enclosing at least k points of a given finite set in a Euclidean space. In the case of a fixed dimension of the space this problem is polynomially solvable, but in general its complexity has not been previously determined. We prove that the problem is NP-hard in the strong sense and obtain a polynomial-time approximation scheme (PTAS) that enables us to solve the problem with an arbitrary relative error ? in time \(O(n^{1/\varepsilon ^2 + 1} d)\), where n is the cardinality of the original set and d is the space dimension.     

A dynamic adaptive local search algorithm for the circular packing problem

This paper studies the circular packing problem (CPP) which consists of packing n non-identical circles C_i of known radius r_i, i ∈ N = {1, … , n}, into the smallest containing circle C. The objective is to determine the coordinates (x_i, y_i) of the center of C_i, i ∈ N, as well as the radius r and center (x, y) of C. This problem, which is a variant of the two-dimensional open dimension problem, is solved using a two-step, dynamic, adaptive, local search algorithm. At each iteration, the algorithm identifies the set of potential “best local positions” of a circle C_i, i ∈ N, given the positions of the previously packed circles, and determines for each of these positions the coordinates and radius of the smallest containing circle. The “best local position” minimizes the radius of the current containing circle. That is, every time an additional circle is packed, both the center and the radius of the containing circle are dynamically updated, and the smallest containing circle is known. The experimental results reflect the good performance of the algorithm.     

Constructions of Solutions to Generalized Sylvester and Fermat–Torricelli Problems for Euclidean Balls

The classical problem of Apollonius is to construct circles that are tangent to three given circles in the plane. This problem was posed by Apollonius of Perga in his work “Tangencies.” The Sylvester problem, which was introduced by the English mathematician J.J. Sylvester, asks for the smallest circle that encloses a finite collection of points in the plane. In this paper, we study the following generalized version of the Sylvester problem and its connection to the problem of Apollonius: given two finite collections of Euclidean balls, find the smallest Euclidean ball that encloses all the balls in the first collection and intersects all the balls in the second collection. We also study a generalized version of the Fermat–Torricelli problem stated as follows: given two finite collections of Euclidean balls, find a point that minimizes the sum of the farthest distances to the balls in the first collection and shortest distances to the balls in the second collection.     

On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls

We consider the outer approximation problem of finding a minimum radius ball enclosing a given intersection of at most n − 1 balls in . We show that if the aforementioned intersection has a nonempty interior, then the problem reduces to minimizing a convex quadratic function over the unit simplex. This result is established by using convexity and representation theorems for a class of quadratic mappings. As a byproduct of our analysis, we show that a class of nonconvex quadratic problems admits a tight semidefinite relaxation.     

Fuzzy disk for covering fuzzy points

In this paper, we consider an important fuzzy version of the well known smallest covering circle problem which is also called the Euclidean 1-center problem. Here we are given a set of points in the plane whose locations are crisp. However, the requirement for coverage of each point is fuzzy as represented by its grade of membership. As such we qualify the points as fuzzy. In the above framework, we wish to find a fuzzy disk with minimum fuzzy area for covering the given fuzzy points. After developing a general model, certain special cases are investigated in detail. Polynomial algorithms are presented for the special cases.     

Optimal rectangle packing

We consider the NP-complete problem of finding an enclosing rectangle of minimum area that will contain a given a set of rectangles. We present two different constraint-satisfaction formulations of this problem. The first searches a space of absolute placements of rectangles in the enclosing rectangle, while the other searches a space of relative placements between pairs of rectangles. Both approaches dramatically outperform previous approaches to optimal rectangle packing. For problems where the rectangle dimensions have low precision, such as small integers, absolute placement is generally more efficient, whereas for rectangles with high-precision dimensions, relative placement will be more effective. In two sets of experiments, we find both the smallest rectangles and squares that can contain the set of squares of size 1×1, 2×2,…,N×N, for N up to 27. In addition, we solve an open problem dating to 1966, concerning packing the set of consecutive squares up to 24×24 in a square of size 70×70. Finally, we find the smallest enclosing rectangles that can contain a set of unoriented rectangles of size 1×2, 2×3, 3×4,…,N×(N+1), for N up to 25.     

Optimal Recovery Methods for Solutions of the Dirichlet Problem that are Exact on Subspaces of Spherical Harmonics

We consider the optimal recovery problem for the solution of the Dirichlet problem for the Laplace equation in the unit d-dimensional ball on a sphere of radius ρ from a finite collection of inaccurately specified Fourier coefficients of the solution on a sphere of radius r, 0 < r < ρ < 1. The methods are required to be exact on certain subspaces of spherical harmonics.

     

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 the geometry of polynomial dynamical systems

In this paper, the author performs a global qualitative study of plane polynomial dynamical systems and suggests a new geometric approach to solving the sixteenth Hilbert problem on the maximum number and mutual location of their limit cycles in two special cases of such systems. First of all, using the geometric properties of four parameters rotating the vector field of a new canonical system constructed in the paper, the author proposes the proof of his early conjecture, which asserts that the maximum number of limit cycles of an arbitrary quadratic system is equal to 4, and their location (3: 1) is uniquely possible [4]. Then using the same geometric approach, the author solves the primary problem for the polynomial Liénard system (in this special case, it is considered as the thirteenth Smale problem), and generalizing the obtained results, the author formulates the theorem on the maximum number of limit cycles enclosing one singular point in the case of a polynomial system. Moreover, applying the Wintner-Perko termination principle for multiple limit cycles, the author develops an alternative approach to solving the sixteenth Hilbert problem, and using this approach, the author completes the global qualitative study of a general cubic Liénard system having three singular points in the finite part of the plane. In conclusion, the author discusses one more known approach to solving the sixteenth Hilbert problem. Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 53, Suzdal Conference-2006, Part 1, 2008.     

Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions

We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case. We apply this bound to obtain a near-cubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3-space. We also present an approximation algorithm for computing a smallest enclosing cylinder. Received May 23, 1997, and in revised form October 20, 1997.     

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.     

Geometric fit of a point set by generalized circles

In our paper we approximate a set of given points by a general circle. More precisely, given two norms k ₁ and k ₂ and a set of points in the plane, we consider the problem of locating and scaling the unit circle of norm k ₁ such that the sum of weighted distances between the circumference of the circle and the given points is minimized, where the distance is measured by a norm k ₂. We present results for the general case. In the case that k ₁ and k ₂ are both polyhedral norms, we are able to solve the problem by investigating a finite candidate set.     

Removing Degeneracy in LP-Type Problems Revisited

LP-type problems is a successful axiomatic framework for optimization problems capturing, e.g., linear programming and the smallest enclosing ball of a point set. In Matoušek and Škovroň (Theory Comput. 3:159–177, 2007), it is proved that in order to remove degeneracies of an LP-type problem, we sometimes have to increase its combinatorial dimension by a multiplicative factor of at least 1+ε with a certain small positive constant ε. The proof goes by checking the unsolvability of a system of linear inequalities, with several pages of calculations. Here by a short topological argument we prove that the dimension sometimes has to increase at least twice. We also construct 2-dimensional LP-type problems with −∞ for which removing degeneracies forces arbitrarily large dimension increase.     

Locating a general minisum ��circle�� on the plane

We approximate a set of given points in the plane by the boundary of a convex and symmetric set which is the unit circle of some norm. This generalizes previous work on the subject which considers Euclidean circles only. More precisely, we examine the problem of locating and scaling the unit circle of some given norm k with respect to given points on the plane such that the sum of weighted distances (as measured by the same norm k) between the circumference of the circle and the points is minimized. We present general results and are able to identify a finite dominating set in the case that k is a polyhedral norm.     

Fuzzy versions of the covering circle problem

In this paper we consider two fuzzy versions of the well-known problem of determining the smallest circle (center and radius) that would cover a given finite set of points in the plane when the locations of points are not precise but fuzzy. The first is modeled as a possibility-constrained mathematical program while the second is modeled as a necessity-constrained one. Polynomial algorithms are presented for both the versions. Also, a numerical example is included for one case. These models and solutions are of interest in both theoretical and practical contexts.