The public defense of Linus Källberg’s doctoral thesis in Computer Science

Doctoral thesis and Licentiate seminars

Datum: 2020-01-10
Tid: 13.15
Plats: room Beta, MDH Västerås.

The public defense of Linus Källberg’s doctoral thesis in Computer Science and Engineering will take place at Mälardalen University, room Beta (Västerås Campus) at 13.15 on January 10, 2020.

Title: “Minimum Enclosing Balls and Ellipsoids in General Dimensions”.

Serial number: 300.

The faculty examiner is Doctor Selin Damla Ahipasaoglu, Singapore University of Technology & Design, Singapore, and the examining committee consists of Professor Ulf Assarsson, Chalmers University och Technology, Professor Anders Forsgren, KTH Royal Institute of Technology and Professor Peter Jonsson, Linköping University.

Reserve; Professor Hans Hansson, Mälardalen University.

Abstract:

The dissertation studies a type of mathematical problem that consists of fitting a simple geometric shape to enclose a given set of data points as tightly as possible. Using simple enclosing shapes to represent or approximate large data sets and detailed geometric structures has a wide range of applications in, e.g., computer graphics, statistics, and machine learning. Efficient methods for computing tight-fitting such shapes are therefore studied extensively in areas such as computational geometry and mathematical optimization.

Two types of enclosing shapes are considered in the thesis: balls and ellipsoids. A ball can also be referred to as a sphere. An ellipsoid, in turn, can be loosely described as a ball that has been "squeezed" and/or "stretched out" along multiple directions. Thus, the specific problems addressed concern how to efficiently find a ball or ellipsoid that has as small a volume as possible, while at the same time fitting a given "cloud" of points completely within its boundary. Because of its more flexible shape, an ellipsoid can approximate the outline of the enclosed point set more accurately than a ball can. On the other hand, the minimum enclosing ellipsoid is more costly to compute and use than the minimum enclosing ball.

The problems are studied in arbitrary dimensions. In only one dimension, both a ball and an ellipsoid are the same as an interval on the number line. In two dimensions, a ball is the same as a circle and an ellipsoid is the same as an ellipse. In more than three dimensions, a ball is most easily described as occupying exactly the space within a certain distance - the radius - from the ball center. This description applies regardless of the number of dimensions of the center and the surrounding space. A high-dimensional ellipsoid, in turn, is most easily described as above, that is, as a squeezed and/or stretched, high-dimensional ball.

The presented research results include new methods for computing a minimum enclosing ball or ellipsoid. The main focus is on handling data sets containing large numbers of points more efficiently than existing methods from the research literature. In addition, a number of techniques are presented to further speed up both the presented methods and some already known methods. Some of these acceleration techniques are based on new theoretical contributions, others make use of modern hardware technologies such as multiple processor cores and graphics processors.