Biggest distance between any two points in a convex hull?
Author
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!
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).
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.
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 ???
Maybe an A* network search implemention ???
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.
Author
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)...
Quote:Original post by Anonymous PosterIndeed, that's bollocks. Consider e.g. an equilateral triangle for the counterexample.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.
Quote:Original post by Christer EricsonI 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.Quote:Original post by Anonymous PosterIndeed, that's bollocks. Consider e.g. an equilateral triangle for the counterexample.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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
