Back to my home page.

On the Smallest Enclosing Information Disk

Frank Nielsen and Richard Nock

Abstract:

In this paper, we present a generalization of the smallest enclosing disk problem for point sets lying in Information-geometric spaces. Given a set of vector points equipped with a (dis)similarity measure that is not necessarily the Euclidean distance, we investigate the problem of finding its center defined as the point minimizing the maximum distance to the point set. For a broad class of distortion measures known as Bregman divergences, these centers are unique and can further be computed efficiently in linear-time by extending the randomized Euclidean algorithm of Welzl [Welzl:1991]. As an application, we show how to solve a statistical model estimation problem by computing the center of a finite set of 1D Normal distributions.  
Key words: computational geometry, smallest enclosing ball, Bregman divergences.  
Bibtex entry:

@inproceedings{nn-cccg-06
, title =       "On the Smallest Enclosing Information Disk"
, author =      "Frank Nielsen and Richard Nock"
, booktitle =   "Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06)"
, site =        "Kingston"
, year =        2006
, pages =       "131--134"
}
YOU NEED TO AUTHORIZE JAVA TO DISPLAY THE APPLET!
THIS IS HOW THE WEB PAGE LOOKS ONCE YOU'LL ALLOW JAVA:

References

Last updated, August 2006.