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.

What is the diameter of an arbitrary 2D figure? (Diameter=The longest distance between two points within the 2D figure). What is the most efficient algorithm? Is it an exact one? Specifically, could we determine the length (at least approximately within some interval $\pm \epsilon$ of the optimal)?

share|improve this question
    
for a polygon (convex & non-convex), it is trivial, such that $O(N^2)$ straightforward solution exists, moreover there is an $O(N)$ solution by using efficient algorithms. I am looking for the answer in 2D shapes in general. –  simco Oct 11 '12 at 1:57
2  
Since you're looking for an algorithm, you must say what kind of input it takes. "2d shapes in general" is not an specification... –  lhf Oct 11 '12 at 2:05
    
The input is an arbitrary 2D geometric figure (e.g. fun-stuff-to-do.com/images/geometric-shapes-to-print-2D.jpg) –  simco Oct 11 '12 at 2:15
2  
Right, but how is it specified? Are you trying to get it physically on a piece of paper, or are you putting a parametric equation into a computer? Why is approximating it as a polygon not sufficient? –  Robert Mastragostino Oct 11 '12 at 2:27
    
Indeed, I know, it is difficult to specify as it is not a polygon, it is not a circle, a semi-circle.. we do not know the input formally, in general. Specifically, could we determine the length of the diameter? –  simco Oct 11 '12 at 2:39
show 2 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.