[math-fun] A completely unrelated question triggered by the word "convex"
Suppose you have a finite set of points in the plane. The process known as "convex peeling" arose as one way of defining the "median" of a finite set of 2-dimensional data, analogous to the usual one for 1-dimensional data: Let the set of points be X. Define X_0 = X and X_(n+1) = X_n - {p in X_n | p is on the boundary of the convex hull of X_n} for n >= 0. This sequential "filtration" of X is known as convex peeling. About 37 year ago someone showed me that if you start with a large number of points uniformly distributed in a square and then proceed to remove them in stages via "convex peeling" — the boundaries of the last groups of points remaining are exceedingly circular. So that there appears to be a true statement, something like: ----- With probability = 1, the shape of the normalized result of convex peeling [toward the end of the process] approaches [in some sense] a circle, as the number of points approaches oo. ----- But I've never seen a proof of this. Any ideas? —Dan
About 37 year ago someone showed me that if you start with a large number of points uniformly distributed in a square and then proceed to remove them in stages via "convex peeling" — the boundaries of the last groups of points remaining are exceedingly circular. ... But I've never seen a proof of this. Any ideas?
I noticed that the furthest point from each point in the set is always part of the convex hull, so the hull is always contained within the intersection of a bunch of circles (where each circle centers at a point and has the furthest point on its circumference). The longest-lived points in the middle in particular draw the smallest circles and tend to confine the hull to a circular shape. Here's an animation of this starting with 2000 points: https://imgur.com/a/Fj8PO And here's the python code I used to generate it: https://pastebin.com/MqPi729n On Tue, Nov 21, 2017 at 10:07 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Suppose you have a finite set of points in the plane.
The process known as "convex peeling" arose as one way of defining the "median" of a finite set of 2-dimensional data, analogous to the usual one for 1-dimensional data:
Let the set of points be X.
Define
X_0 = X
and X_(n+1) = X_n - {p in X_n | p is on the boundary of the convex hull of X_n}
for n >= 0. This sequential "filtration" of X is known as convex peeling.
About 37 year ago someone showed me that if you start with a large number of points uniformly distributed in a square and then proceed to remove them in stages via "convex peeling" — the boundaries of the last groups of points remaining are exceedingly circular.
So that there appears to be a true statement, something like: ----- With probability = 1, the shape of the normalized result of convex peeling [toward the end of the process] approaches [in some sense] a circle, as the number of points approaches oo. -----
But I've never seen a proof of this. Any ideas?
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
(Dan and I continued the conversation off-list. Here are some other distributions we toyed with) rand() ^ 5: https://imgur.com/a/TCzcN biased only in x: https://imgur.com/a/lnUOC Symmetrical (neat "eye of Sauron" sort of look): https://imgur.com/a/nf9je And here I tried peeling furthest points instead of convex hulls. Does seem to stay more circular, eating away at the y axis and preserving width better: https://imgur.com/a/C60sY On Sat, Nov 25, 2017 at 10:37 PM, Jason Holt <credentiality@gmail.com> wrote:
About 37 year ago someone showed me that if you start with a large number
of points uniformly distributed in a square and then proceed to remove them in stages via "convex peeling" — the boundaries of the last groups of points remaining are exceedingly circular. ... But I've never seen a proof of this. Any ideas?
I noticed that the furthest point from each point in the set is always part of the convex hull, so the hull is always contained within the intersection of a bunch of circles (where each circle centers at a point and has the furthest point on its circumference). The longest-lived points in the middle in particular draw the smallest circles and tend to confine the hull to a circular shape. Here's an animation of this starting with 2000 points:
And here's the python code I used to generate it:
On Tue, Nov 21, 2017 at 10:07 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Suppose you have a finite set of points in the plane.
The process known as "convex peeling" arose as one way of defining the "median" of a finite set of 2-dimensional data, analogous to the usual one for 1-dimensional data:
Let the set of points be X.
Define
X_0 = X
and X_(n+1) = X_n - {p in X_n | p is on the boundary of the convex hull of X_n}
for n >= 0. This sequential "filtration" of X is known as convex peeling.
About 37 year ago someone showed me that if you start with a large number of points uniformly distributed in a square and then proceed to remove them in stages via "convex peeling" — the boundaries of the last groups of points remaining are exceedingly circular.
So that there appears to be a true statement, something like: ----- With probability = 1, the shape of the normalized result of convex peeling [toward the end of the process] approaches [in some sense] a circle, as the number of points approaches oo. -----
But I've never seen a proof of this. Any ideas?
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Nice animations! A little experimentation suggests that a uniform distribution on any convex polygon tends toward ellipses centered at the original polygon's center of gravity; in the limit this should somehow become an "optimal" contraction of the polygon to a point? On Sun, Nov 26, 2017 at 8:06 PM, Jason Holt <credentiality@gmail.com> wrote:
(Dan and I continued the conversation off-list. Here are some other distributions we toyed with)
rand() ^ 5: https://imgur.com/a/TCzcN
biased only in x: https://imgur.com/a/lnUOC
Symmetrical (neat "eye of Sauron" sort of look): https://imgur.com/a/nf9je
And here I tried peeling furthest points instead of convex hulls. Does seem to stay more circular, eating away at the y axis and preserving width better: https://imgur.com/a/C60sY
On Sat, Nov 25, 2017 at 10:37 PM, Jason Holt <credentiality@gmail.com> wrote:
About 37 year ago someone showed me that if you start with a large number
of points uniformly distributed in a square and then proceed to remove them in stages via "convex peeling" — the boundaries of the last groups of points remaining are exceedingly circular. ... But I've never seen a proof of this. Any ideas?
I noticed that the furthest point from each point in the set is always part of the convex hull, so the hull is always contained within the intersection of a bunch of circles (where each circle centers at a point and has the furthest point on its circumference). The longest-lived points in the middle in particular draw the smallest circles and tend to confine the hull to a circular shape. Here's an animation of this starting with 2000 points:
And here's the python code I used to generate it:
On Tue, Nov 21, 2017 at 10:07 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Suppose you have a finite set of points in the plane.
The process known as "convex peeling" arose as one way of defining the "median" of a finite set of 2-dimensional data, analogous to the usual one for 1-dimensional data:
Let the set of points be X.
Define
X_0 = X
and X_(n+1) = X_n - {p in X_n | p is on the boundary of the convex hull of X_n}
for n >= 0. This sequential "filtration" of X is known as convex peeling.
About 37 year ago someone showed me that if you start with a large number of points uniformly distributed in a square and then proceed to remove them in stages via "convex peeling" — the boundaries of the last groups of points remaining are exceedingly circular.
So that there appears to be a true statement, something like: ----- With probability = 1, the shape of the normalized result of convex peeling [toward the end of the process] approaches [in some sense] a circle, as the number of points approaches oo. -----
But I've never seen a proof of this. Any ideas?
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Dan Asimov -
Jason Holt -
Michael Collins