[math-fun] 2D convex hull
convex hull of N points in 2D (or in 3D) can be computed in O(NlogN) steps and that is best possible in certain models of computation (e.g. algebraic decision tree model). There are many algorithms, perhaps the simplest are "randomized incremental" where you add points in random order, updating a convex hullish data structure as you go and for those algorithms the O(NlogN) is only in expectation over the randomness. For 2D, you need only to compute 3x3 determinant-signs in exact arithmetic (sign of area of a triangle), also expressible using 2x2 determinants. In general a primitive to compute sign of (D+1)x(D+1) determinant will suffice.
A simple question in 3-space, but I'm not sure it can be solved in closed form: Let C denote a cube of side 2 centered at the origin. Let S(r) denote the sphere of radius r centered at the origin. QUESTION: For which r does the area of S(r) lying inside of C reach its absolute maximum? (Of course any maximizing r satisfies 1 <= r <= sqrt(3).) --Dan
For 0 < r < 1 trivially the area A(r) increases towards A(1) = 4 pi > 12 . For 1 < r < sqrt(2) the area of a spherical cap cut off exceeds the area of the circle where the sphere meets the cube, so A(1 + x) - A(1) < 4 pi r^2 - 6 pi (r^2 - 1) - 4 pi = 4 pi (1 + 2 x + x^2) - 6 pi (2 x + x^2) - 4 pi = - 2 pi (2 x + x^2) < 0 , and A(r) inceeds A(1) . For sqrt(2) < r < sqrt(3) the area of a spherical trigon nestling in a cube corner inceeds the area of the trihedron enclosing it; at r = sqrt(2) the trihedra have max total area 6*4 - 6*2 = 12 , which inceeds A(1) . For r > sqrt(3) trivially A = 0 . Hence A has maximum at r = 1 . WFL On 8/10/13, Dan Asimov <dasimov@earthlink.net> wrote:
A simple question in 3-space, but I'm not sure it can be solved in closed form:
Let C denote a cube of side 2 centered at the origin. Let S(r) denote the sphere of radius r centered at the origin.
QUESTION: For which r does the area of S(r) lying inside of C reach its absolute maximum?
(Of course any maximizing r satisfies 1 <= r <= sqrt(3).)
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Fred, I apologize, since I think I now see my mistake: I overlooked the less-than sign < between A(1 + x) - A(x) and the following expression. (I thought it was an equals sign -- very careless of me.) Sorry about that. --Dan On 2013-08-10, at 3:50 PM, Fred Lunnon wrote:
For 0 < r < 1 trivially the area A(r) increases towards A(1) = 4 pi > 12 .
For 1 < r < sqrt(2) the area of a spherical cap cut off exceeds the area of the circle where the sphere meets the cube, so A(1 + x) - A(1) < 4 pi r^2 - 6 pi (r^2 - 1) - 4 pi = 4 pi (1 + 2 x + x^2) - 6 pi (2 x + x^2) - 4 pi = - 2 pi (2 x + x^2) < 0 , and A(r) inceeds A(1) .
For sqrt(2) < r < sqrt(3) the area of a spherical trigon nestling in a cube corner inceeds the area of the trihedron enclosing it; at r = sqrt(2) the trihedra have max total area 6*4 - 6*2 = 12 , which inceeds A(1) .
For r > sqrt(3) trivially A = 0 .
Hence A has maximum at r = 1 .
WFL
On 8/10/13, Dan Asimov <dasimov@earthlink.net> wrote:
A simple question in 3-space, but I'm not sure it can be solved in closed form:
Let C denote a cube of side 2 centered at the origin. Let S(r) denote the sphere of radius r centered at the origin.
QUESTION: For which r does the area of S(r) lying inside of C reach its absolute maximum?
(Of course any maximizing r satisfies 1 <= r <= sqrt(3).)
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I meant to say: Very nice solution, Fred! --Dan On 2013-08-11, at 1:04 AM, Dan Asimov wrote:
Fred,
I apologize, since I think I now see my mistake: I overlooked the less-than sign < between A(1 + x) - A(x) and the following expression. (I thought it was an equals sign -- very careless of me.)
Sorry about that.
--Dan
On 2013-08-10, at 3:50 PM, Fred Lunnon wrote:
For 0 < r < 1 trivially the area A(r) increases towards A(1) = 4 pi > 12 .
For 1 < r < sqrt(2) the area of a spherical cap cut off exceeds the area of the circle where the sphere meets the cube, so A(1 + x) - A(1) < 4 pi r^2 - 6 pi (r^2 - 1) - 4 pi = 4 pi (1 + 2 x + x^2) - 6 pi (2 x + x^2) - 4 pi = - 2 pi (2 x + x^2) < 0 , and A(r) inceeds A(1) .
For sqrt(2) < r < sqrt(3) the area of a spherical trigon nestling in a cube corner inceeds the area of the trihedron enclosing it; at r = sqrt(2) the trihedra have max total area 6*4 - 6*2 = 12 , which inceeds A(1) .
For r > sqrt(3) trivially A = 0 .
Hence A has maximum at r = 1 .
WFL
On 8/10/13, Dan Asimov <dasimov@earthlink.net> wrote:
A simple question in 3-space, but I'm not sure it can be solved in closed form:
Let C denote a cube of side 2 centered at the origin. Let S(r) denote the sphere of radius r centered at the origin.
QUESTION: For which r does the area of S(r) lying inside of C reach its absolute maximum?
(Of course any maximizing r satisfies 1 <= r <= sqrt(3).)
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The argument below for sqrt(2) < r < sqrt(3) could do with fleshing out. Consider a pyramidal sliver with vertex at the origin, intersecting the spherical trigon and a face of the cube in a pair of corresponding surface elements. Let sphere equator be chosen parallel to cube face, with p,q = longtitude, latitude. The spherical element has area r cos q dp r dq = (r^2 cos q) dp dq ; the planar element has area cot q dp csc^2 q dq = (cos q / sin^3 q) dp dq . Now sin q < 1/r since the caps are cut off by the cube faces, so the ratio of area elements = r^2 sin^3 q < 1 ; integrating, the area of the spherical trigon inceeds the area of the corner trihedron. WFL On 8/10/13, Fred Lunnon <fred.lunnon@gmail.com> wrote:
For 0 < r < 1 trivially the area A(r) increases towards A(1) = 4 pi > 12 .
For 1 < r < sqrt(2) the area of a spherical cap cut off exceeds the area of the circle where the sphere meets the cube, so A(1 + x) - A(1) < 4 pi r^2 - 6 pi (r^2 - 1) - 4 pi = 4 pi (1 + 2 x + x^2) - 6 pi (2 x + x^2) - 4 pi = - 2 pi (2 x + x^2) < 0 , and A(r) inceeds A(1) .
For sqrt(2) < r < sqrt(3) the area of a spherical trigon nestling in a cube corner inceeds the area of the trihedron enclosing it; at r = sqrt(2) the trihedra have max total area 6*4 - 6*2 = 12 , which inceeds A(1) .
For r > sqrt(3) trivially A = 0 .
Hence A has maximum at r = 1 .
WFL
On 8/10/13, Dan Asimov <dasimov@earthlink.net> wrote:
A simple question in 3-space, but I'm not sure it can be solved in closed form:
Let C denote a cube of side 2 centered at the origin. Let S(r) denote the sphere of radius r centered at the origin.
QUESTION: For which r does the area of S(r) lying inside of C reach its absolute maximum?
(Of course any maximizing r satisfies 1 <= r <= sqrt(3).)
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Dan Asimov -
Fred Lunnon -
Warren D Smith