Bouncing Bubble: A fast algorithm for Minimal Enclosing Ball problem - Tapa blanda

Tian, Bo

 
9783656326991: Bouncing Bubble: A fast algorithm for Minimal Enclosing Ball problem
Tapa blanda
ISBN 10: 3656326991 ISBN 13: 9783656326991
Editorial: GRIN Verlag, 2012

Sinopsis

Scientific Essay from the year 2012 in the subject Computer Science - Theory, , language: English, abstract: In this paper, a new algorithm for solving MEB problem is proposed based on new understandings on the geometry property of minimal enclosing ball problem. A substitution of Ritter's algorithm is proposed to get approximate results with higher precision, and a 1+ϵ approximation algorithm is presented to get the approximation with specified precision within much less time comparing with present algorithms. Like Ritter's algorithm, this algorithm iterates over all points and increase the radius gradually. However, the algorithm does not try to cover all seen points in each step, instead, it will create a new ball (or circle in 2D case) to just touch the new point and cover half of the existing ball. This approach makes sure that the new ball is always increasing in its size and still be smaller than the optimal ball. And finally, a Ritter's algorithm is applied to ensure every point is covered. The result is an approximate solution to the MEB problem. The radius is usually just slightly bigger than the optimal solution (around 1%) instead (5~20% with Ritter's algorithm). This paper also explained how to compute 1+ϵ approximation solution, where ϵ is specified to a given precision.

"Sinopsis" puede pertenecer a otra edición de este libro.

Reseña del editor

Scientific Essay from the year 2012 in the subject Computer Science - Theory, , language: English, abstract: In this paper, a new algorithm for solving MEB problem is proposed based on new understandings on the geometry property of minimal enclosing ball problem. A substitution of Ritter's algorithm is proposed to get approximate results with higher precision, and a 1+ϵ approximation algorithm is presented to get the approximation with specified precision within much less time comparing with present algorithms. Like Ritter's algorithm, this algorithm iterates over all points and increase the radius gradually. However, the algorithm does not try to cover all seen points in each step, instead, it will create a new ball (or circle in 2D case) to just touch the new point and cover half of the existing ball. This approach makes sure that the new ball is always increasing in its size and still be smaller than the optimal ball. And finally, a Ritter's algorithm is applied to ensure every point is covered. The result is an approximate solution to the MEB problem. The radius is usually just slightly bigger than the optimal solution (around 1%) instead (5~20% with Ritter's algorithm). This paper also explained how to compute 1+ϵ approximation solution, where ϵ is specified to a given precision.

"Sobre este título" puede pertenecer a otra edición de este libro.

Editorial
GRIN Verlag
Año de publicación
2012
Idioma
Inglés
ISBN 10 
3656326991
ISBN 13 
9783656326991
Encuadernación
Tapa blanda
Número de edición
3
Número de páginas
24
Contacto del fabricante
GRIN Publishing GmbH
info@grin.com

Waltherstraße 23
München
80337
Alemania