• Advertisement
Sign in to follow this  

Biggest distance between any two points in a convex hull?

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

If you intended to correct an error in the post then please contact us.

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 this post


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

Share this post


Link to post
Share on other sites
Quote:
Original post by deffer
And 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 this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Zahlman
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).


I dont think that this assumption will hold.



Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
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).


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

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


True, take an equilateral triangle, for example.

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Quote:
Original post by Zahlman
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).

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

Share this post


Link to post
Share on other sites
Quote:
Original post by Christer Ericson
Quote:
Original post by Anonymous Poster
Quote:
Original post by Zahlman
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).

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.

Share this post


Link to post
Share on other sites
Assume the length of each edge of the convex hull is roughly constant, so the perimeter is O(n) where n is the number of points on the convex hull. Also assume you have unlimited resources.

Take a sufficiently large piece of wood, and use a jigsaw to cut out a shape matching the convex hull. If you cut at a constant rate around the perimeter of the convex hull, that will take O(n) time. Stand the cut section of wood on its edge (also an O(n) operation since the energy required to lift it will be proportional to the height of the centre of mass above the ground, and the height will be proportional to n). Hold a long flat ruler above it horizontally, resting on the top. Roll the section of wood along the ground. When there is a point where it was pushing the ruler upwards but then started moving downwards, hold the ruler in place until it's pushed upwards again. Continue for a full revolution, i.e. a distance proportional to the perimeter (with a constant amount of work as you move along) and thus O(n). Now measure the height of the ruler above the ground, and that should give you the maximum distance in O(n).

I suppose you could do the same in a computer, but that's no fun.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement