Jump to content
  • Advertisement
Sign in to follow this  
sir_wojciech

Biggest distance between any two points in a convex hull?

This topic is 4218 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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!