[math-fun] Robust convex closure
Suppose you want to distribute a small given finite number of points around the origin of the Cartesian plane so that the origin is in the interior of the convex closure of the points. It's easy - you can't do it with two points, but you can do it with three. Now suppose you want to ensure that the origin will still be inside the convex closure even if one of the points is removed by an evil entity. I have pretty much convinced myself that you can't do it with four points, though I would appreciate a clear proof. You can do it with five; a regular pentagon centered on the origin clearly works. Now what if the evil entity is allowed to remove any two points? How many points do you need to be safe? I think the answer is six (a regular hexagon works). Seven points defends against three removals, but I think you might need nine to defend against four. I suspect the answer in general is that you need more than twice as many points as the evil entity is allowed to remove, but I don't have a proof.
If you can't do one-point-removal with four (because, for two opposite points, the origin cannot be on both sides of a line connecting them), then how can you do two-point-removal with a hexagon (two opposite points, origin can't be on both sides)? Don't you mean removing 1 point takes 5, removing two points takes 7, removing three points takes 9, and so on? On Tue, Nov 21, 2017 at 3:39 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Suppose you want to distribute a small given finite number of points around the origin of the Cartesian plane so that the origin is in the interior of the convex closure of the points. It's easy - you can't do it with two points, but you can do it with three.
Now suppose you want to ensure that the origin will still be inside the convex closure even if one of the points is removed by an evil entity. I have pretty much convinced myself that you can't do it with four points, though I would appreciate a clear proof. You can do it with five; a regular pentagon centered on the origin clearly works.
Now what if the evil entity is allowed to remove any two points? How many points do you need to be safe? I think the answer is six (a regular hexagon works).
Seven points defends against three removals, but I think you might need nine to defend against four. I suspect the answer in general is that you need more than twice as many points as the evil entity is allowed to remove, but I don't have a proof. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
You're right, a regular hexagon fails. I'm sure this little problem will fall to an argument that involves running a line through the origin, counting the points on both sides, and rotating the line to see how the counts change. On Tue, Nov 21, 2017 at 6:44 PM, Tomas Rokicki <rokicki@gmail.com> wrote:
If you can't do one-point-removal with four (because, for two opposite points, the origin cannot be on both sides of a line connecting them), then how can you do two-point-removal with a hexagon (two opposite points, origin can't be on both sides)? Don't you mean removing 1 point takes 5, removing two points takes 7, removing three points takes 9, and so on?
On Tue, Nov 21, 2017 at 3:39 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Suppose you want to distribute a small given finite number of points around the origin of the Cartesian plane so that the origin is in the interior of the convex closure of the points. It's easy - you can't do it with two points, but you can do it with three.
Now suppose you want to ensure that the origin will still be inside the convex closure even if one of the points is removed by an evil entity. I have pretty much convinced myself that you can't do it with four points, though I would appreciate a clear proof. You can do it with five; a regular pentagon centered on the origin clearly works.
Now what if the evil entity is allowed to remove any two points? How many points do you need to be safe? I think the answer is six (a regular hexagon works).
Seven points defends against three removals, but I think you might need nine to defend against four. I suspect the answer in general is that you need more than twice as many points as the evil entity is allowed to remove, but I don't have a proof. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If you're removing n points, a regular 2n+3-gon works. If you only have 2n+2 points, label them p_1, p_2, p_3, p_{2n+2} in order by increasing theta in polar coordinates. Rotate the plane so that theta(p_0) = 0. If p_{n+2} has nonnegative y coordinate, then so do p{i}, 1 <= i <= n+2, so removing p_{n+3} through p_{2n + 2} leaves a convex hull in the upper half-plane. If p_{n+2} has nonpositive y coordinate, then so do p{i}, n+2<= i <= 2n+2 and p_1, so removing p_{2} through p_{n + 1} leaves a convex hull in the lower half-plane. We've proved something slightly stronger than needed; we can choose one favorite point (p_1) that the evil entity is not allowed to remove, and it can still thwart us. Andy On Wed, Nov 22, 2017 at 7:17 AM, Allan Wechsler <acwacw@gmail.com> wrote:
You're right, a regular hexagon fails. I'm sure this little problem will fall to an argument that involves running a line through the origin, counting the points on both sides, and rotating the line to see how the counts change.
On Tue, Nov 21, 2017 at 6:44 PM, Tomas Rokicki <rokicki@gmail.com> wrote:
If you can't do one-point-removal with four (because, for two opposite points, the origin cannot be on both sides of a line connecting them), then how can you do two-point-removal with a hexagon (two opposite points, origin can't be on both sides)? Don't you mean removing 1 point takes 5, removing two points takes 7, removing three points takes 9, and so on?
On Tue, Nov 21, 2017 at 3:39 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Suppose you want to distribute a small given finite number of points around the origin of the Cartesian plane so that the origin is in the interior of the convex closure of the points. It's easy - you can't do it with two points, but you can do it with three.
Now suppose you want to ensure that the origin will still be inside the convex closure even if one of the points is removed by an evil entity. I have pretty much convinced myself that you can't do it with four points, though I would appreciate a clear proof. You can do it with five; a regular pentagon centered on the origin clearly works.
Now what if the evil entity is allowed to remove any two points? How many points do you need to be safe? I think the answer is six (a regular hexagon works).
Seven points defends against three removals, but I think you might need nine to defend against four. I suspect the answer in general is that you need more than twice as many points as the evil entity is allowed to remove, but I don't have a proof. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- Andy.Latto@pobox.com
On 11/22/17, Andy Latto <andy.latto@pobox.com> wrote:
If you're removing n points, a regular 2n+3-gon works.
If you only have 2n+2 points, label them p_1, p_2, p_3, p_{2n+2} in order by increasing theta in polar coordinates. Rotate the plane so that theta(p_0) = 0.
If p_{n+2} has nonnegative y coordinate, then so do p{i}, 1 <= i <= n+2, so removing p_{n+3} through p_{2n + 2} leaves a convex hull in the upper half-plane.
If p_{n+2} has nonpositive y coordinate, then so do p{i}, n+2<= i <= 2n+2 and p_1, so removing p_{2} through p_{n + 1} leaves a convex hull in the lower half-plane.
We've proved something slightly stronger than needed; we can choose one favorite point (p_1) that the evil entity is not allowed to remove, and it can still thwart us.
Andy
On Wed, Nov 22, 2017 at 7:17 AM, Allan Wechsler <acwacw@gmail.com> wrote:
You're right, a regular hexagon fails. I'm sure this little problem will fall to an argument that involves running a line through the origin, counting the points on both sides, and rotating the line to see how the counts change.
On Tue, Nov 21, 2017 at 6:44 PM, Tomas Rokicki <rokicki@gmail.com> wrote:
If you can't do one-point-removal with four (because, for two opposite points, the origin cannot be on both sides of a line connecting them), then how can you do two-point-removal with a hexagon (two opposite points, origin can't be on both sides)? Don't you mean removing 1 point takes 5, removing two points takes 7, removing three points takes 9, and so on?
On Tue, Nov 21, 2017 at 3:39 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Suppose you want to distribute a small given finite number of points around the origin of the Cartesian plane so that the origin is in the interior of the convex closure of the points. It's easy - you can't do it with two points, but you can do it with three.
Now suppose you want to ensure that the origin will still be inside the convex closure even if one of the points is removed by an evil entity. I have pretty much convinced myself that you can't do it with four points, though I would appreciate a clear proof. You can do it with five; a regular pentagon centered on the origin clearly works.
Now what if the evil entity is allowed to remove any two points? How many points do you need to be safe? I think the answer is six (a regular hexagon works).
Seven points defends against three removals, but I think you might need nine to defend against four. I suspect the answer in general is that you need more than twice as many points as the evil entity is allowed to remove, but I don't have a proof. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The (3,4,5) triangle has sides in arithmetic progression. I was curious in what dimensions can the sides and main diagonal of a rectangular box be in arithmetic progression. Here's what I found. In 2 dimensions, all solutions are multiples of (3,4,5). In 3, 4, and 5 dimensions, arithmetic progression is possible only when the lengths are allowed to be quadratic surds. In 6 or more dimensions, arithmetic progression requires complex lengths. -- Gene
participants (5)
-
Allan Wechsler -
Andy Latto -
Eugene Salamin -
Fred Lunnon -
Tomas Rokicki