4
$\begingroup$

I have a closed bounded convex shape in $\mathbb{R}^3$. I want to calculate what I would call the minimal diameter: find the plane (or, generally, the space of codimension 1) which minimizes the maximum distance from points in the shape to the plane, then take that maximum distance. I suppose one should take the supremum if the set is not closed.

How can I find this efficiently? And is there a standard name for it? It seems too obvious to be without a name.

I'm particularly interested in the case that the shape is a conic section or otherwise defined by low-degree polynomial inequalities.

  • 0
    @Thomas: The i$n$terior is completely filled. As for the plane: take the set of all planes (not necessarily containing the origin). For each plane, find a point in the set which is furthest from the plane and measure the distance (or take the supremum, if no point is furthest -- but this doesn't happen in my case). Select a plane which minimizes this distance; that distance is what I have called the minimum diameter. But surely there is a name for it.2012-07-11

3 Answers 3

5

Up to the factor of 2, this is known as the minimum width, and sometimes simply as the width of a convex body. Another, and perhaps clearer definition of it is: the length of the shortest projection onto a line. Unfortunately I do not know anything about the algorithmic side of the issue.

  • 0
    Ah, I misunderstood then. Good! The paper you suggested references http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9977 which seems to answer my question. Thanks!2012-07-11
5

An algorithm for this was described in a 1988 paper, "Computing the Width of a Set" by Michael Houle and his then advisor, Godfried Toussaint (CiteSeer link; IEEE journal link). Their algorithm runs in $O(n^2)$ time for a polyhedron of $n$ vertices, or more precisely, in $O(n+I)$ time, where $I$ is the number of antipodal edge pairs. They prove a theorem characterizing the parallel planes that might realize the width, which leads to this time complexity.

  • 2
    I just realized this same paper was cited in a comment via a raw URL.2012-07-12
1

Only some remarks not fitting into a comment, but intended as a comment: what you describe (and explain more precisely in your comment) will give you something which I'd call the minimal radius, since you allow your planes to intersect the convex set. For 'diameter' I'd restrict to planes not intersecting the interior of the convex set. That is what I then would actually call diameter of the set. Of course these two should simply differ by a factor of 2. This (the minimal radius) is, for example, the geometric quantity you need if you want to estimate what time it takes to boil an egg, cause you need to calculate the amount of time it takes till every part of the egg is above a certain temperature ;-)

(What you want to do is a minimax search, that is you are looking for critical points of a certain functional which are neither global minima nor maxima, which is, in general, usually not completely trivial and a topic considered in Nonlinear functional analyis. Look, e.g., at Deimlings book on Nonlinear FA. For your specific problem this may be a bit too much firing power, but depending on your mathematical skills maybe you'll find it to be of interest. If only for terminology. I do not know about algorithms for this kind of problem, though I'm sure there are some. Note though, that you do not seem to be looking at sets with smooth boundary, which may imply additional complications. This is just a gut feeling of me, though.)