New code for smallest enclosing balls

[Bernd Gaertner]

  A new C++ code for computing the smallest enclosing ball
of points in d-dimensional Euclidean space is now available
from my web page, at

	http://www.inf.ethz.ch/personal/gaertner/miniball.html

  Some of you might know that I maintain and distribute (upon
request) code for this problem already for quite some time (to
be precise, for eight years), but only now has it reached a level
of robustness that allows me to release it officially. 

  The main new features of the code are the following:

	- very fast in low dimensions due to improved primitive
	  operations and template programming; the dimension is
	  fixed at compile-time, allowing the compiler to unroll
	  time-critical loops. 

	- improved performance in higher dimensions. While the
	  previously best method -- Emo Welzl's move-to-front
	  heuristic -- quits in dimension 20, my code can solve
	  large problems up to dimension 30. In dimension 20,
	  it's by a factor of 40 faster.

	- increased numerical stability. All computations are
	  done in standard floating-point arithmetic, but most
	  input degeneracies previously found to be critical 
	  (cospherical points, multiple points, points close 
	  together) are now routinely handled. 

	- compact, readable and understandable code. The code
	  itself is small (about 300 lines, excluding prototypes
	  and test suite) and comes with full documentation 
	  following the literate programming paradigm. This
	  means, the code is part of the documentation and not
	  the other way round. 

	- Support of major platforms. I have tested Microsoft 
	  Visual C++, GNU and EGCS as well as MIPS (SGI), but
	  it should be easy to adapt to other recent platforms. 
	  In the future, the code will become part of CGAL, the
	  European Computational Geometry Algorithms Library.

   If you are interested, simply download the code from the above
address - it's free for non-commercial use. I would be glad about
any feedback that helps me to further improve the code.

   Best regards,
		Bernd Gaertner. 
 
	

	

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.