CGAL users discussion list

[Atul Thakur <>]

Hi everyone,

I have a general geometry question as follows.

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.

I am trying to approach it as an optimization problem. My approach is
as follows.

1. Express the point where the sphere touches the triangular facet in
terms of barycentric coordinates

P_touch = alpha*X_1 + beta*X_2 + gamma*X_3

alpha, beta, gamma are unknown. X_1, X_2, X_3 are vertices of queried
facet and known.

2. The center of sphere must lie on the normal of triangular facet
passing through the P_touch.

Express center of sphere as:
P_center = P_touch + normal*R

where, normal is normal vector and known, R is radius of sphere and unknown.

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

Problem with 4 variables(alpha, beta, gamma, R) and 8 constraints.

I guess solving above optimization problem can give me the answer but
is there a smart way to solve this problem that I am missing using
some existing geometric constructs like Voronoi cells. Any pointers
would be really helpful.

thanks,

-Atul