SERIE B--- INFORMATIK Smallest Enclosing Ellipses-- Fast and

The problem of finding the smallest enclosing ellipsoid of an n-point set P in d-space is an instance of convex programming and can be solved by general methods in time O(n) if the dimension is fixed. The problem-specific parts of these methods are encapsu

SERIE B| INFORMATIK

Smallest Enclosing Ellipses{ Fast and Exact *Bernd Gartnery Sven Schonherrz

B 97-03 May 1997

The problem of nding the smallest enclosing ellipsoid of an n-point set P in d-space is an instance of convex programming and can be solved by general methods in time O(n) if the dimension is xed. The problem-speci c parts of these methods are encapsulated in primitive operations that deal with subproblems of constant size. We derive explicit formulae for the primitive operations of Welzl's randomized method 22] in dimension d= 2. Compared to previous ones, these formulae are simpler and faster to evaluate, and they only contain rational expressions, allowing for an exact solution.

Abstract

* supported by the ESPRIT IV LTR Project No. 21957 (CGAL), a preliminary version appeared in Proc. 13th Annu. ACM Symp. on Computational Geometry (SoCG), 1997 8] y Institut fur Theoretische Informatik, ETH Zurich, Haldeneggsteig 4, CH-8092 Zurich, Switzerland, e-mail: gaertner@inf.ethz.ch z Institut fur Informatik, Freie Universitat Berlin, Takustr. 9, D-14195 Berlin, Germany, e-mail: sven@inf.fu-berlin.de

The problem of finding the smallest enclosing ellipsoid of an n-point set P in d-space is an instance of convex programming and can be solved by general methods in time O(n) if the dimension is fixed. The problem-specific parts of these methods are encapsu

2

1 IntroductionThe unique ellipsoid of smallest volume enclosing a compact set P in d-space (also known as the Lowner-John ellipsoid of P 10]) has appealing mathematical properties which make it theoretically interesting and practically useful. In typical applications, a complicated body needs to be covered by a simple one of similar shape and volume, in order to simplify certain tests. For convex bodies (e.g. the convex hull of a nite point set), the smallest enclosing ellipsoid{ unlike the isothetic bounding box or the smallest enclosing sphere{ guarantees a volume approximation ratio that is independent of the shape of the covered body. This follows from the following property of it, rst proved by John (who also established existence and uniqueness) 10]: if the smallest enclosing ellipsoid of a compact convex body K is scaled about its center with factor 1=d, the resulting ellipsoid lies completely inside K . Let us mention three concrete applications.

Ray tracing. Given a scene of objects in 3-space and a ray, nd the rst object hit by the ray. This problem occurs in computer graphics, when the scene is rendered in presence of various light sources. Since many rays need to be processed, the query has to be answered fast. In order to test whether a given object is hit by a ray, we can rst test with a bounding volume (which we have precomputed){ if the ray misses it, it misses the object as well 7, section 15.10.2]. As bounding volumes, boxes, spheres but also ellipsoids 3] are useful, depending on the kind of objects.a collision-free motion of a robot among a set of obstacles is sought. After enclosing the robot and/or the obstacles by simple shapes, the problem becomes easier, and if a valid motion is found in the simpli ed environment, this motion is also valid in the original setting. It is clear that this heuristic is the

more successful, the tighter the bounding volumes approximate the objects 4].

Motion planning. In a similar spirit, bounding volumes are applied in robotics, when

Statistics. In a di erent way, the smallest enclosing ellipsoid is applied in statistics. Given a cloud of measure points in d-space, one wants to identify and peel o`outliers', often repeatedly. One heuristic peels o the vertices of the convex hull 2]. A ner peeling is obtained by choosing the boundary points of the smallest enclosing ellipsoid 18], whose number typically depends only on d.1.1 Previous Work

Several algorithms for computing the smallest enclosing ellipsoid of an n-point set in d-space have been proposed. On the one hand, there are iterative methods which employ standard optimization techniques (such as gradient descent), adapted to the problem 21, 17]. These algorithms usually work on a dual problem, known as D-optimal design 20]. On the other hand, there are nite methods which nd the desired ellipsoid within a bounded number of steps. For xed d, the algorithm of Post 15] has complexity O(n2 ). An optimal deterministic O(n) algorithm has been given by Dyer 6], randomized O(n) methods are due to Adler and Shamir 1] and Welzl 22]. Since the problem is LP-type in

The problem of finding the smallest enclosing ellipsoid of an n-point set P in d-space is an instance of convex programming and can be solved by general methods in time O(n) if the dimension is fixed. The problem-specific parts of these methods are encapsu

SMALLEST ENCLOSING ELLIPSES{ FAST AND EXACT

3

the sense of 12], generic algorithms for this class of problems can be applied as well, see 9]. In any case, the runtime dependence on d is exponential. A method for the case d= 2, without time analysis, has been developed by Silverman and Titterington 18]. All these nite methods have the property that actual work is done only for problem instances whose size is bounded by a function in d. Assuming that d is constant, such instances can be solved in constant time. However, as far as explicit formulae for these primitive operations have been given{ which is the case only for d= 2{ they are quite complicated and rely on solving third-degree polynomials 18, 14, 16]. This makes them expensive to evaluate and only leads to approximate solutions, unless specialized number types allowing exact manipula …… 此处隐藏：34052字，全部文档内容请下载后查看。喜欢就下载吧 ……