Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I have to admit I do not understand your definition of minimal diameter. By plane, do you mean plane containing the origin? Why do you think that you can talk about 'the' plane (as opposed to 'some plane')? Does your convex set have nonempty interior? –  user20266 Jul 11 '12 at 17:17
    
@Thomas: The interior 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. –  Charles Jul 11 '12 at 17:31

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
Ah, yes, I actually want that rather than what I asked for. Is there a literature? –  Charles Jul 11 '12 at 18:27
2  
@Charles Apparently, yes –  user31373 Jul 11 '12 at 18:35
    
Wait, I take it back. It's related to what I want, but missing a crucial feature. Suppose the shape was a flat box one foot by one foot by one inch. I want the answer to be one inch, not one foot. (The answer I originally asked for would be one-half inch.) –  Charles Jul 11 '12 at 19:10
    
@Charles The minimum width of your box is one inch. –  user31373 Jul 11 '12 at 19:14
    
Ah, I misunderstood then. Good! The paper you suggested references citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9977 which seems to answer my question. Thanks! –  Charles Jul 11 '12 at 19:17

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.

share|improve this answer
2  
I just realized this same paper was cited in a comment via a raw URL. –  Joseph O'Rourke Jul 12 '12 at 1:17

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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.