| |
 |
|
|
Science Forum Index » Mathematics Forum » Largest ball in a convex polyhedron
Page 1 of 1
|
| Author |
Message |
| Søren Holbech |
 Posted: Thu Dec 18, 2003 4:31 am |
|
|
|
Guest
|
Hi
I'm trying to find the largest ball I can fit into a convex polyhedron,
represented as the intersection of a number of halfspaces. I guess that
the center of mass of the polyhedron might be used as the coordinates of
the center of this ball, and that the radius is then simply found by
minimizing distance to the halfplanes defining the polyhedron.
However, as this is merely a guess at a method, I would be most grateful
if someone could state whether it is correct, and perhaps provide a
pointer to some theorem.
Alternatively, if someone knows a simpler method I would love to hear
about it.
Sincerely
Søren Nielsen |
|
|
| Back to top |
|
| David C. Ullrich |
| Posted: Thu Dec 18, 2003 7:36 am |
|
|
|
Guest
|
On Thu, 18 Dec 2003 10:31:26 +0100, Søren Holbech <holbech@cs.auc.dk>
wrote:
Quote: Hi
I'm trying to find the largest ball I can fit into a convex polyhedron,
represented as the intersection of a number of halfspaces. I guess that
the center of mass of the polyhedron might be used as the coordinates of
the center of this ball, and that the radius is then simply found by
minimizing distance to the halfplanes defining the polyhedron.
However, as this is merely a guess at a method, I would be most grateful
if someone could state whether it is correct, and perhaps provide a
pointer to some theorem.
Your method is certainly not correct. (For example imagine a
polyhedron that looks more or less like a very long thin cone;
the largest ball is going to touch the base, while the center
of mass is far from the base.)
Quote: Alternatively, if someone knows a simpler method I would love to hear
about it.
I doubt that there exists a simple method to give the exact answer.
Quote: Sincerely
Søren Nielsen
************************
David C. Ullrich |
|
|
| Back to top |
|
| Larry Hammick |
| Posted: Thu Dec 18, 2003 7:51 am |
|
|
|
Guest
|
"Søren Holbech"
Quote: I'm trying to find the largest ball I can fit into a convex polyhedron,
represented as the intersection of a number of halfspaces. I guess that
the center of mass of the polyhedron might be used as the coordinates of
the center of this ball, and that the radius is then simply found by
minimizing distance to the halfplanes defining the polyhedron.
That cannot be the whole answer. If we start with a polyhedron and its
maximal sphere, we can snip away a small amount of the polyhedron, at one of
its vertices, by adding one more halfspace; the center of mass of the
polyhedron will change, but the sphere will stay the same.
The centre of the sphere will be equidistant from at least four of the
planes. I suppose one could calculate that distance for each four-element
set of planes, and then just take the biggest.
LH |
|
|
| Back to top |
|
| David Eppstein |
| Posted: Thu Dec 18, 2003 10:54 am |
|
|
|
Guest
|
In article <BphEb.105837$bC.26909@clgrps13>,
"Larry Hammick" <larryhammick@telus.net> wrote:
Quote: The centre of the sphere will be equidistant from at least four of the
planes. I suppose one could calculate that distance for each four-element
set of planes, and then just take the biggest.
This is a linear program: find (x,y,z,d) such that, for each plane P,
the distance from (x,y,z) to the plane is at most d (two linear
constraints), maximizing d (linear objective function).
Since it is a linear program with a constant number of variables, it can
be solved in time linear in the number of planes (your suggestion would
instead take O(n^4).
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science |
|
|
| Back to top |
|
| David Eppstein |
| Posted: Thu Dec 18, 2003 6:04 pm |
|
|
|
Guest
|
In article <eppstein-59803E.07540518122003@news.service.uci.edu>,
David Eppstein <eppstein@ics.uci.edu> wrote:
Quote: The centre of the sphere will be equidistant from at least four of the
planes. I suppose one could calculate that distance for each four-element
set of planes, and then just take the biggest.
This is a linear program: find (x,y,z,d) such that, for each plane P,
the distance from (x,y,z) to the plane is at most d (two linear
constraints), maximizing d (linear objective function).
Oops, distance from (x,y,z) to P should be at least d, not at most.
Fortunately we know which side of P is inside the polyhedron so this is
still a linear constraint.
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science |
|
|
| Back to top |
|
| Christer Ericson |
| Posted: Fri Dec 19, 2003 2:13 am |
|
|
|
Guest
|
In article <pan.2003.12.18.09.31.25.433100@cs.auc.dk>, holbech@cs.auc.dk
says...
Quote: I'm trying to find the largest ball I can fit into a convex polyhedron,
represented as the intersection of a number of halfspaces [...]
Such a ball is determined by the _Chebyshev center_ and the
smallest distance from this center to the supporting halfplane
of your halfspaces. The Chebyshev center can be found using
linear programming in linear time.
For more detail, see chapter 7 (Geometrical problems) of
Boyd and Vandenberghe's _Convex Optimization_, as available
here:
http://www.devdept.com/tod/books.php
http://www.ee.ucla.edu/~vandenbe/cvxbook.html
Christer Ericson
Sony Computer Entertainment, Santa Monica |
|
|
| Back to top |
|
| Søren Holbech Nielsen |
| Posted: Sat Dec 20, 2003 12:02 pm |
|
|
|
Guest
|
Hi again
Thanks for the suggestions and the correction of my mistake. In addition
to the replies in this thread, I also received a mail from Brian Borchers
suggesting linear programming for solving the problem. Another mail I
received presented a different take on the subject, and is quoted below
for completeness.
Sincerely
Søren Nielsen
QUOTE
From jferry@csar.uiuc.edu Sat Dec 20 18:00:09 2003
Date: Thu, 18 Dec 2003 13:33:03 -0600 (CST)
From: James P. Ferry <jferry@csar.uiuc.edu>
To: holbech@cs.auc.dk
Subject: Re: Largest ball in a convex polyhedron
Hi Soren,
I'm e-mailing because I don't have access to post to newsgroups
right now. (You can post this e-mail if for some reason that
helps.) I thought of a fairly simple algorithm, but you'll have
to fill in the details yourself.
The important thing to realize is that in any convex set S, if B0
and B1 are two balls that fit in S (individually, that is, not
together), then B(t) = (1-t) B0 + t B1 can be fit in S for any
0 <= t <= 1. The center and radius of B(t) are
x(t) = (1-t) x0 + t x1 and r(t) = (1-t) r0 + t r1, respectively,
where x0, x1, r0, and r1 are the centers and radii of B0 and B1.
Let v0 = x'(t) = x1 - x0, and w0 = r'(t) = r1 - r0. We can then
write B(t) as
x(t) = x0 + v0 t, and r(t) = r0 + w0 t.
For the algorithm, you need to code 3 key functions:
(1) Given a ball B0 = (x0,r0) in S, does there exist (v0,w0) with
w0 > 0 such that B(t) is in S for some t > 0?
(2) If the answer to (1) is yes, provide some (v0,w0).
(3) If the answer to (1) is yes, and given the (v0,w0) from (2),
find the largest t for which B(t) is in S.
B0 is maximal if and only if the answer to (1) is "no". Intuitively
it seems like the answer is "yes" if and only if there exists a closed
hemisphere of B0 which does not intersect the surface of S.
The algorithm, then, is to loop over asking (1), and if "yes", then to
perform (2) and (3) to get a B(t) of larger radius, and then to set
B0 = B(t). This algorithm gives a sequence of larger and larger spheres.
It should terminate in a finite number of steps when S is a polyhedron
(I think).
I don't have time to work out the details, but I'm confident that this
idea is a good way to go. Maybe it reduces to applying the simplex
method for (David Eppstein's formulation of the problem as) a linear
program, but this seems more intuitive to me. (Then again, I dislike
linear programming.)
-Jim
| Jim Ferry | http://www.uiuc.edu/ph/www/jferry/ |
+-----------------------+ jferry@[delete_this]uiuc.edu |
| Center for Simulation | (217) 333-8985 (Office) |
| of Advanced Rockets | (217) 333-1910 (Fax) |
\QUOTE |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Thu Aug 21, 2008 4:56 pm
|
|