IJPAM: Volume 51, No. 4 (2009)


R. Enkhbat$^1$, A. Bayarbaatar$^2$, W. Hwang$^3$
$^{1,2}$School of Mathematics and Computer Science
National University of Mongolia
P.O. Box 46635, Ulaanbaatar, 210646, MONGOLIA
$^3$Inje University
#64 Joedon 2-Ga, Chung-Gu, Seoul, KOREA

Abstract.Geometry problems of finding inscribed or circumscribed balls defined over a polyhedral set are classical. It is known that finding minimal ellipsoid circumscribing a polytope is NP-hard [#!HP95!#]. Many combinatorial, clustering, data mining, and pattern recognition problems require to find a ball set circumscribing a given set. On the other hand, from computational point of view, it is interesting to find a center of a ball inscribed in a given set defined by a system of linear inequalities. In this paper, we consider a problem of finding the maximum and minimum radiuses of inscribed and circumscribed balls defined over a polyhedral set. We formulate the above problem as optimization problems and then propose some algorithms for solving them.

Received: November 28, 2008

AMS Subject Classification: 74P99

Key Words and Phrases: polyhedral, minimal ellipsoid circumscribing,

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2009
Volume: 51
Issue: 4