Jump to content
  • Advertisement
Sign in to follow this  

Biggest distance between any two points in a convex hull?

This topic is 4133 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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!