CGAL users discussion list

[Bernd Gaertner <>]

Atul Thakur wrote:
> A polyhedron (non-convex with triangles as its bounding facets) is
> given. For a given facet determine the maximum sized sphere that is
> tangential to the facet and contained completely inside the
> polyhedron.
[snip]
> 3. Solve following optimization problem:
>
> Maximize R
>
> S.T.
> nR^2 - Sum[(x_j - P_center) dot(x_j - P_center) ] >= 0 (as all points
> x_j lying on the polyhedron surface lie outside or on the sphere)
> 0<alpha, beta, gamma<1
> R>0

This optimization problem is no good. A sphere can be penetrating a 
facet even if it does not has any of the points inside. And by summing 
up constraints, you will have them satisfied only "on average" but not 
individually.

Best,
Bernd.