ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 29 Apr 2020 09:47:25 +0200Find the center of a maximum inscribed sphere of a convex polytopehttps://ask.sagemath.org/question/50952/find-the-center-of-a-maximum-inscribed-sphere-of-a-convex-polytope/Is there a way in SageMath to find the center of the (or of some, if not unique) sphere of maximum radius which is inside of a convex polytope? I ask the question in general dimension, but I am currently interested in a solution in dimension 2.Thu, 23 Apr 2020 11:57:31 +0200https://ask.sagemath.org/question/50952/find-the-center-of-a-maximum-inscribed-sphere-of-a-convex-polytope/Answer by Sébastien for <p>Is there a way in SageMath to find the center of the (or of some, if not unique) sphere of maximum radius which is inside of a convex polytope? I ask the question in general dimension, but I am currently interested in a solution in dimension 2.</p>
https://ask.sagemath.org/question/50952/find-the-center-of-a-maximum-inscribed-sphere-of-a-convex-polytope/?answer=50972#post-id-50972It's ok, I found the solution using MILP:
def center_inscribed_sphere_polytope(polytope, solver=None):
r"""
Return the center and radius of maximal inscribed sphere
INPUT:
- ``polytope`` -- polytope
OUTPUT:
a 2-tuple (center, radius)
EXAMPLES::
sage: P = polytopes.associahedron(['A',3])
sage: center_inscribed_sphere_polytope(P)
([0.03553390593273766, 0.5355339059327378, 0.03553390593273766],
1.4644660940672622)
sage: center_inscribed_sphere_polytope(P + vector((10,10,10)))
([10.035533905932738, 10.535533905932738, 10.035533905932738],
1.4644660940672622)
::
sage: P = Polyhedron([(0,0), (1,0), (0,10)])
sage: center_inscribed_sphere_polytope(P)
([0.47506218943955486, 0.47506218943955486], 0.47506218943955486)
"""
from math import sqrt
from sage.numerical.mip import MixedIntegerLinearProgram
p = MixedIntegerLinearProgram(solver=solver)
x = p.new_variable()
d = p.new_variable()
for ineq in polytope.inequalities_list():
constant = ineq[0]
coeffs = ineq[1:]
norm = sqrt(sum(a**2 for a in coeffs))
S = p.sum(a/norm*x[i] for (i,a) in enumerate(coeffs))
p.add_constraint(constant/norm + S >= d[0])
p.set_objective(d[0])
radius = p.solve()
soln = p.get_values(x)
center = [soln[k] for k in sorted(x.keys())]
return center, radius
Thu, 23 Apr 2020 22:52:44 +0200https://ask.sagemath.org/question/50952/find-the-center-of-a-maximum-inscribed-sphere-of-a-convex-polytope/?answer=50972#post-id-50972Comment by Sébastien for <p>It's ok, I found the solution using MILP:</p>
<pre><code>def center_inscribed_sphere_polytope(polytope, solver=None):
r"""
Return the center and radius of maximal inscribed sphere
INPUT:
- ``polytope`` -- polytope
OUTPUT:
a 2-tuple (center, radius)
EXAMPLES::
sage: P = polytopes.associahedron(['A',3])
sage: center_inscribed_sphere_polytope(P)
([0.03553390593273766, 0.5355339059327378, 0.03553390593273766],
1.4644660940672622)
sage: center_inscribed_sphere_polytope(P + vector((10,10,10)))
([10.035533905932738, 10.535533905932738, 10.035533905932738],
1.4644660940672622)
::
sage: P = Polyhedron([(0,0), (1,0), (0,10)])
sage: center_inscribed_sphere_polytope(P)
([0.47506218943955486, 0.47506218943955486], 0.47506218943955486)
"""
from math import sqrt
from sage.numerical.mip import MixedIntegerLinearProgram
p = MixedIntegerLinearProgram(solver=solver)
x = p.new_variable()
d = p.new_variable()
for ineq in polytope.inequalities_list():
constant = ineq[0]
coeffs = ineq[1:]
norm = sqrt(sum(a**2 for a in coeffs))
S = p.sum(a/norm*x[i] for (i,a) in enumerate(coeffs))
p.add_constraint(constant/norm + S >= d[0])
p.set_objective(d[0])
radius = p.solve()
soln = p.get_values(x)
center = [soln[k] for k in sorted(x.keys())]
return center, radius
</code></pre>
https://ask.sagemath.org/question/50952/find-the-center-of-a-maximum-inscribed-sphere-of-a-convex-polytope/?comment=51135#post-id-51135I don't know if the above can be changed to find the center of the John ellipsoid instead?
https://en.wikipedia.org/wiki/John_ellipsoidWed, 29 Apr 2020 09:47:25 +0200https://ask.sagemath.org/question/50952/find-the-center-of-a-maximum-inscribed-sphere-of-a-convex-polytope/?comment=51135#post-id-51135