Top

Published in:

2016 | OriginalPaper | Chapter

A Filtering Heuristic for the Computation of Minimum-Volume Enclosing Ellipsoids

Authors : Linus Källberg, Thomas Larsson

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study heuristics to accelerate existing state-of-the-art algorithms for the minimum-volume enclosing ellipsoid problem. We propose a new filtering heuristic that can significantly reduce the number of distance computations performed in algorithms derived from Khachiyan’s first-order algorithm. Our experiments indicate that in high dimensions, the filtering heuristic is more effective than the elimination heuristic proposed by Harman and Pronzato. In lower dimensions, the elimination heuristic is superior.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Using Unified Model Checking to Verify Heaps

next chapter Relaxations of Discrete Sets with Semicontinuous Variables

Ahipaşaoğlu, S.D., Yıldırım, E.A.: Identification and elimination of interior points for the minimum enclosing ball problem. SIAM J. Optim. 19(3), 1392–1396 (2008)MathSciNetCrossRefMATH

Barnett, V.: The ordering of multivariate data. J. Roy. Stat. Soc. Ser. A (Gen.) 139(3), 318–355 (1976)MathSciNetCrossRef

Betke, U., Henk, M.: Approximating the volume of convex bodies. Discret. Comput. Geom. 10(1), 15–21 (1993)MathSciNetCrossRefMATH

Bouville, C.: Bounding ellipsoids for ray-fractal intersection. In: Proceedings of SIGGRAPH 1985, pp. 45–52. ACM (1985)

Chazelle, B., Matoušek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21(3), 579–597 (1996)MathSciNetCrossRefMATH

Ding, J., Zhou, A.: Eigenvalues of rank-one updated matrices with some applications. Appl. Math. Lett. 20(12), 1223–1226 (2007)MathSciNetCrossRefMATH

Galkovskyi, T., Gärtner, B., Rublev, B.: The domination heuristic for LP-type problems. In: Proceedings of the Meeting on Algorithm Engineering and Experiments, pp. 74–84. Society for Industrial and Applied Mathematics (2009)

Harman, R., Pronzato, L.: Improvements on removing nonoptimal support points in \(D\)-optimum design algorithms. Stat. Probab. Lett. 77(1), 90–94 (2007)MathSciNetCrossRefMATH

John, F.: Extremum problems with inequalities as subsidiary conditions. In: Studies and Essays, Presented to R. Courant on His 60th Birthday, pp. 187–204. Wiley Interscience (1984)

10.

Källberg, L., Larsson, T.: Faster approximation of minimum enclosing balls by distance filtering and GPU parallelization. J. Graph. Tools 17(3), 67–84 (2013)CrossRef

11.

Källberg, L., Larsson, T.: Improved pruning of large data sets for the minimum enclosing ball problem. Graph. Models 76(6), 609–619 (2014)CrossRef

12.

Khachiyan, L.G.: Rounding of polytopes in the real number model of computation. Math. Oper. Res. 21(2), 307–320 (1996)MathSciNetCrossRefMATH

13.

Kumar, P., Yildirim, E.A.: Minimum-volume enclosing ellipsoids and core sets. J. Optim. Theor. Appl. 126(1), 1–21 (2005)MathSciNetCrossRefMATH

14.

Liu, S., Wang, C.C.L., Hui, K.-C., Jin, X., Zhao, H.: Ellipsoid-tree construction for solid objects. In: Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling, pp. 303–308 (2007)

15.

Rimon, E., Boyd, S.P.: Obstacle collision detection using best ellipsoid fit. J. Intell. Rob. Syst. 18(2), 105–126 (1997)CrossRefMATH

16.

Sun, P., Freund, R.M.: Computation of minimum-volume covering ellipsoids. Oper. Res. 52(5), 690–706 (2004)MathSciNetCrossRefMATH

17.

Titterington, D.M.: Optimal design: some geometrical aspects of \(D\)-optimality. Biometrika 62(2), 313–320 (1975)MathSciNetCrossRefMATH

18.

Titterington, D.M.: Estimation of correlation coefficients by ellipsoidal trimming. Appl. Stat. 27(3), 227–234 (1978)MathSciNetCrossRefMATH

19.

Todd, M.J., Yıldırım, E.A.: On Khachiyan’s algorithm for the computation of minimum-volume enclosing ellipsoids. Discret. Appl. Math. 155(13), 1731–1744 (2007)CrossRefMATH

20.

Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: Maurer, H. (ed.) New Results and New Trends in Computer Science. LNCS, vol. 555, pp. 359–370. Springer, Heidelberg (1991)CrossRef

21.

Yıldırım, E.A.: On the minimum volume covering ellipsoid of ellipsoids. SIAM J. Optim. 17(3), 621–641 (2006)MathSciNetCrossRefMATH

Title: A Filtering Heuristic for the Computation of Minimum-Volume Enclosing Ellipsoids
Authors: Linus Källberg
Thomas Larsson
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-48748-9

Electronic ISBN: 978-3-319-48749-6

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-48749-6_56

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner