Points on convex hulls
Author
Suppose I have a set of points S. I would like to construct the convex hull S* of S. It turns out that |S| is large, so it would be nice if I could take a few shortcuts by making some assumptions. However, I'm having some trouble deciding which of these assumptions is true. I looked up a few papers and this list subsequently got shorter, but there's still some lingering ones I haven't cleared up. Can you guys help me out?
[Proposition 1] If a point p in S* is furthest from q in S* and vice versa, then the segment pq forms the diameter of S*.
[Proposition 2: Specific] Suppose points p, q, r are all in S*. If prq represents points on a boundary path along S*, and q is the first local maximum for p on the boundary path, then none of the points other than q along that path can be a local maximum for r.
[Proposition 2: General] Suppose points p, q, r, s are all in S*. If prsq represents points on a boundary path along S* such that d[p,s] <= d[p,q], then d[r, s] <= d[r, q].
[Edited by - kSquared on November 30, 2004 8:52:25 PM]
I don't understand your post, and I am a geometrist, so chances are that actually you didn't explain things well. I don't understand what the purpose of the "Propositions" is, or the precise meaning of their wording.
Look up a Graham Scan on goggle. It runs in nlogn time, so you wont get much better than that unless you know anything in particular about the data you enter.
proposition 1, just means if i interpret correctly, that if you have the largest distance between two points on the convex hull, then this distance is the diameter of the encompassing sphere.
proposition 2 specific, means that if you have the path like you describe, r is a maximum because it is the middle point on the path. If there would be another maximum, the convex hull would be different going through the other local maximum, this is a contradiction
proposition 2 general, looks like some shift in point positions, but seems logical for a convex path.
proposition 2 specific, means that if you have the path like you describe, r is a maximum because it is the middle point on the path. If there would be another maximum, the convex hull would be different going through the other local maximum, this is a contradiction
proposition 2 general, looks like some shift in point positions, but seems logical for a convex path.
Quote:Original post by Airo
proposition 1, just means if i interpret correctly, that if you have the largest distance between two points on the convex hull, then this distance is the diameter of the encompassing sphere.
That's not what he said. The diameter of S* is by definition the lowest upper bound of the distances between two points of S*. If S* is compact (and it is if S is finite), then the maximum and the lowest upper bound are the same thing, so property one is guaranteed.
Quote:proposition 2 specific, means that if you have the path like you describe, r is a maximum because it is the middle point on the path. If there would be another maximum, the convex hull would be different going through the other local maximum, this is a contradiction
A maximum? A maximum of what? Am I missing something?
Quote:proposition 2 general, looks like some shift in point positions, but seems logical for a convex path.
Well, I guess I am confused by previous errors, like some compilers might say, but I am not even sure of what we are talking about. Is he trying to see if there are faster algorithms for computing the convex hull of sets S that satisfy some extra conditions? Or what?
Author
Quote:Original post by alvaroQuote:Original post by Airo
proposition 1, just means if i interpret correctly, that if you have the largest distance between two points on the convex hull, then this distance is the diameter of the encompassing sphere.
That's not what he said. The diameter of S* is by definition the lowest upper bound of the distances between two points of S*. If S* is compact (and it is if S is finite), then the maximum and the lowest upper bound are the same thing, so property one is guaranteed.Quote:proposition 2 specific, means that if you have the path like you describe, r is a maximum because it is the middle point on the path. If there would be another maximum, the convex hull would be different going through the other local maximum, this is a contradiction
A maximum? A maximum of what? Am I missing something?Quote:proposition 2 general, looks like some shift in point positions, but seems logical for a convex path.
Well, I guess I am confused by previous errors, like some compilers might say, but I am not even sure of what we are talking about. Is he trying to see if there are faster algorithms for computing the convex hull of sets S that satisfy some extra conditions? Or what?
I guess there was confusion about what I was saying, so let me clarify. Sorry if you misunderstood, alvaro. I'll try to be as clear as possible this time around.
Forget that I'm interested in this for algorithmic purposes. The real reason I posted is because I'm having trouble deciding if these statements are true, as I said in the OP:
Quote:However, I'm having some trouble deciding which of these assumptions is true.
Any help you can give me in deciding the truth or falsity of the propositions would be appreciated. The above-mentioned statements are:
Quote:[Proposition 1] If a point p in S* is furthest from q in S* and vice versa, then the segment pq forms the diameter of S*.
The question behind this statement is, "Suppose I select any point p known to be on the hull, and that q is on the hull and is the farthest point from p. Also suppose that q is farthest from p. Does this mean that pq is the diameter of the convex hull?"
Quote:[Proposition 2: Specific] Suppose points p, q, r are all in S*. If prq represents points on a boundary path along S*, and q is the first local maximum for p on the boundary path, then none of the points other than q along that path can be a local maximum for r.
I screwed up here and left out a key clause; the original statement's been edited and I include it here (bolded portion is changed part). This statement asks: "I pick points p, q, r from the hull and I form a boundary path prq from them. If q is a local maximum for p, then none of the other points on the path prq can be a local maximum for p."
You mentioned that you were confused by the term 'local maximum'. In terms of geometry, a point P on the boundary of a polygon is a local maximum for another point Q on the boundary iff the boundary points on either side of Q are closer to P than Q is to P. I apologize if I was using unfamiliar terms.
Quote:[Proposition 2: General] Suppose points p, q, r, s are all in S*. If prsq represents points on a boundary path along S* such that d[p,s] <= d[p,q], then d[r, s] <= d[r, q].
This statement asks the question: "Suppose I pick points p, q, r, s from the hull and I form a boundary path prsq from them. Is it true that if d(p,s) <= d(p,q), then d(r,s) <= d(r,q)?"
Hope that cleared things up. Sorry for the confusion.
I can quickly tell you that Proposition 1 is false.
S={(0,1),(1,0),(0,-1),(-.95,0)}
Pick p=(1,0). The point that is the furthest away from it is q=(-.95,0), and p is the point that is the furthest away from p. Yet 1.95 is not the diameter of the set; 2 is.
S={(0,1),(1,0),(0,-1),(-.95,0)}
Pick p=(1,0). The point that is the furthest away from it is q=(-.95,0), and p is the point that is the furthest away from p. Yet 1.95 is not the diameter of the set; 2 is.
Quote:Original post by kSquared
[Proposition 2: Specific] Suppose points p, q, r are all in S*. If prq represents points on a boundary path along S*, and q is the first local maximum for p on the boundary path, then none of the points other than q along that path can be a local maximum for r.
If i understand right, counterexample is:
Draw such shape:
_________q_________/ \k .\_________p_______r_/ .and k is placed on "\"
You can place r and k that k is local maximum to r.
Yet first (and only) local maximum to p is q.
edit: misinterpreted maximum as minimum :(
Quote:
[Proposition 2: General] Suppose points p, q, r, s are all in S*. If prsq represents points on a boundary path along S* such that d[p,s] <= d[p,q], then d[r, s] <= d[r, q].
d[p,q] is a distance?
and i guess, you meant to say them must be necessarily in that order, prsq?
[wrong attempts to prove removed]
edit2: and forget about S* .
You just have convex polygon prsq , and s is closer to p than q.
If you prove that for convex polygon prsq, you prove your proposition too, because any prsq is convex if it is your path. If you find counterexample for that polygon, it is also counterexample for your proposition.
edit3: oh, damn, it's so simple to prove using what i said in "edit2"!
Proving:
draw line A orthogonal to sq through center of sq. Line defines 2 halfspaces, points that is closer to q is in one halfspace, and closer to s is in other halfspace.
q is in halfspace that is closer to q, obviously. And both p and s is in halfspace that is closer to s. (for s, obviously, for d , by your proposition)
Therefore both pq and sq intersect line A. And convex can intersect line only in 0 or 2 points*. If r is in other halfspace than s, there will be 4 intersections therefore it is not convex.
[unnecessary: if not wrong 1&2, i would prove 3 alot faster...]
So i disproved 2nd(edit:my wrong understanding of it , not 2nd! ) and proved 3rd proposition...
Grammarnazing and rewording proof of 3rd proposition(rewording work with "=" cases **) is left as exercise of reader[grin]...
(*) : for me, tangent lines do not intersect it.
(**) : just replace "ih halfspace..." by "in halfspace or on the line A..." , and so-on, if needed.
[Edited by - Dmytry on December 1, 2004 7:55:53 AM]
Author
Quote:Original post by DmytryQuote:Original post by kSquared
[Proposition 2: Specific] Suppose points p, q, r are all in S*. If prq represents points on a boundary path along S*, and q is the first local maximum for p on the boundary path, then none of the points other than q along that path can be a local maximum for r.
If i understand right, counterexample is:
Draw such shape:_________q_________/ \k .\_________p_______r_/ .
and k is placed on "\"
I think you might have misread the statement. To disprove it, you'd have to show that when q is the local maximum for p, there exists a point other than q on the path which is the local maximum for r.
Quote:You can place r and k that k is local maximum to r.
Yet first (and only) local maximum to p is q.
Umm... q is looking awfully like the local maximum for r in your diagram, not k. If anything, k looks like the local minimum!
Quote:So i disproved 2nd and proved 3rd proposition...
Also, since the third statement is a more general case of the second statement, it is impossible to prove the third statement without also proving the second. So I'm a little wary of your "proof" right now even though I can't see anything wrong with it at first glance.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
