# Biggest distance between any two points in a convex hull?

This topic is 4287 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Any idea how to calculate the biggest distance between any two points in a convex hull in time smaller than O(n^2) (if yes -> please explain the idea)? Thanks in advance!

##### Share on other sites
And this is not a homework... because you need it for... what, exactly? [smile]

##### Share on other sites
If the convex hull is 2d, then rotating calipers.

##### Share on other sites
Quote:
 Original post by defferAnd this is not a homework... because you need it for... what, exactly? [smile]

I would guess he wants to create a bounding circle for the collection of points (the line connecting the two furthest-apart points on the hull would be a diameter of the circle).

##### Share on other sites
Quote:
 Original post by ZahlmanI would guess he wants to create a bounding circle for the collection of points (the line connecting the two furthest-apart points on the hull would be a diameter of the circle).

I dont think that this assumption will hold.

##### Share on other sites
A possible use for 'Swarm Intelligence' type solution using adjacency information of edges and vertices and using distance from other discobered extremity points as the criteria ????

Maybe an A* network search implemention ???

##### Share on other sites
Quote:
 Original post by ZahlmanI would guess he wants to create a bounding circle for the collection of points (the line connecting the two furthest-apart points on the hull would be a diameter of the circle).

I'm being suspicious, since it's a common algorithmic problem on my Uni.

Quote:
 Original post by Anonymous PosterI dont think that this assumption will hold.

True, take an equilateral triangle, for example.

##### Share on other sites
Thanks for all your replies. I'll check the rotating calipers. And I don't need this for homework, just been doing some exercises for myself and this problem arose (and I'm too young for Uni anyways)...

##### Share on other sites
Quote:
Original post by Anonymous Poster
Quote:
 Original post by ZahlmanI would guess he wants to create a bounding circle for the collection of points (the line connecting the two furthest-apart points on the hull would be a diameter of the circle).

I dont think that this assumption will hold.
Indeed, that's bollocks. Consider e.g. an equilateral triangle for the counterexample.

##### Share on other sites
Quote:
Original post by Christer Ericson
Quote:
Original post by Anonymous Poster
Quote:
 Original post by ZahlmanI would guess he wants to create a bounding circle for the collection of points (the line connecting the two furthest-apart points on the hull would be a diameter of the circle).

I dont think that this assumption will hold.
Indeed, that's bollocks. Consider e.g. an equilateral triangle for the counterexample.
I would have guessed the same thing as Zahlman. Even though I knew already that it wouldn't work, it is very likely that the original poster might think it would work.
If he had come back and said that that was what he was doing, then we would break the news to him at that moment.

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5

• 13
• 10
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632995
• Total Posts
3009775
• ### Who's Online (See full list)

There are no registered users currently online

×