Paper: Approximating Smallest Enclosing Balls

Approximating Smallest Enclosing Balls

Frank Nielsen and Richard Nock

Abstract:
We present two novel tailored algorithms for computing arbitrary fine approximations of the smallest enclosing ball of balls. The deterministic heuristics are based on solving relaxed decision problems using a primal-dual method.

Key words: smallest enclosing ball, approximation, high dimensions.

ICCSA CGA 2004 paper (PDF, 224 KB) © Springer-Verlag. The original publication is available at SpringerLink.
CCCG 2004 paper (PDF)

Bibtex entry:


@InProceedings{nn-aseb-2004,
	editor    = {Frank Nielsen and Richard Nock},
	title = {Approximating Smallest Enclosing Balls},
	author= {Frank Nielsen and Richard Nock},
	booktitle     = {Proceedings of International Conference on Computational Science and Its Applications (ICCSA)},
	publisher = {Springer},
	series    = {Lecture Notes in Computer Science},
	volume    = {3045},
	page = {147-157}
	year      = {2004}
}


@InProceedings{nn-ased-2004,
	editor    = {Frank Nielsen and Richard Nock},
	title = {Approximating Smallest Enclosing Disks},
	author= {Frank Nielsen and Richard Nock},
	booktitle     = {Proceedings of 16th Canadian Conference on Computational Geometry (CCCG)},
	year      = {2004}
}

We provide an implementation for point sets or disk sets.

Publication:

Frank Nielsen and Richard Nock,
Approximating Smallest Enclosing Balls,
International Conference on Computational Science and Its Applications (ICCSA),
International Workshop on Computational Geometry and Its Applications (CGA),
LNCS, Springer, 2004.

Frank Nielsen and Richard Nock,
Approximating Smallest Enclosing Disks,
16th Canadian Conference on Computational Geometry (CCCG), 2004.

Last updated, 2004.