# IJPAM: Volume 51, No. 4 (2009)

**OPTIMIZATION APPROACH FOR SOLVING**

SOME GEOMETRY PROBLEMS

SOME GEOMETRY PROBLEMS

School of Mathematics and Computer Science

National University of Mongolia

P.O. Box 46635, Ulaanbaatar, 210646, MONGOLIA

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