Comment by thaumasiotes | Hacker News Reader

Comment by thaumasiotes | Hacker News Reader

Parent Full thread

> This process (consider every triangle and compute the smallest area) gives you a function which takes an arrangement of points and returns a number. Now ask which arrangement of points gives the biggest such number. This is the biggest smallest triangle problem and it appears to be very (very very very) difficult.

You must have left out part of the problem? If the question is "given a square, identify the set of points for which this function will return the largest number", that immediately reduces to the problem of "what is the largest triangle that can be inscribed inside a square?" (because there is no possible advantage to including more than three points in your set).

It looks like the problem is actually a derivative of the function you described - if your function is f(A) [where A is any set of points in the unit square], then what we want is a function g(n), for integer n >= 3, which gives us the maximum value taken by f when f is restricted to sets that contain exactly n points?

The part of the problem left out is that you cannot choose the number of points, only their arrangement. Given n, choose an arrangement of n points in the square that maximises the area of the largest smallest triangle.

This is not trivial. It sounds like one can just arrange 3 points to form a very large triangle and then put the rest of the points away in a corner, but then the smallest triangle will be between some of the points in the corner, not your conveniently large one.

> This is not trivial.

I never thought it was! I'm having enough trouble trying to prove that the largest triangle that will fit in a square is half the size of the square.

Claim one: all 3 points lie on the edges. Proof: if one doesn't, one can enlarge the area of the triangle by moving it along one of the edges of the current triangle, away from the other point on that edge, until it hits a border of the square.

Then take one vertex that is not in a square corner yet. The area of the triangle is 1/2 * (length of opposite edge) * (distance from opposite edge to this vertex). This can be written as a linear function of the position of this vertex along the square edge it is on. Thus over all positions of the vertex on this square-edge, the area either is always the same (if the opposite triangle edge is parallel to this square-edge), or the area is maximised by putting this vertex in a square corner.

Repeat this process three times. Conclusion: the obvious half-square triangle has maximal area (even if it is not unique with that property), so the maximal area is half the square's area.

> Thus over all positions of the vertex on this square-edge, the area either is always the same (if the opposite triangle edge is parallel to this square-edge), or the area is maximised by putting this vertex in a square corner.

I'm sure this is correct, but the proof doesn't seem ironclad. As far as I see, you're relying on the idea that moving two vertices jointly, as one operation, can't produce any benefits relative to moving the two vertices in sequence one after the other. And while I have no reason to doubt that that's correct, it isn't obvious to me.

(Wording it another way - how do you prove that [the position of vertex B on the edge of the square] that maximizes the area of the triangle holding the position of vertex C fixed is the same as [the position of vertex B on the edge of the square] that maximizes the area of the triangle holding only the edge to which vertex C is attached fixed?)

I know this is not how proofs work, but is is quite intuitive. What is the point we stop proving things that look obvious and axiomatic?

The question is, how big is the smallest triangle, not how big is the biggest triangle.

The (smaller) question is the area of the smallest triangle defined by the set of points.

Then, above that, there's the question of which set of points defines the largest smallest triangle.

Adding points to the set can only ever shrink the size of the smallest triangle that the set defines. So if you're free to add or remove points, you will always maximize the size of the smallest triangle by going all the way down to three points. At that point, you can't remove any more, but you're still free to rearrange them, so you're asking the question "what is the largest triangle that can be inscribed in a square?".

Why did you respond to me? What did you think you were saying?

> Adding points to the set can only ever shrink the size of the smallest triangle that the set defines.

I don’t think this is true. Any 3 points almost in a line will have a very small area. Adding points inside the triangle would help, and bisecting a small angle, a point on that line would work would work even outside of the triangle, for a ways anyway. I can think of a few other examples.

Most points won’t help though.

>> Adding points to the set can only ever shrink the size of the smallest triangle that the set defines.

> I don’t think this is true. Any 3 points almost in a line will have a very small area. Adding points inside the triangle would help

Come on. Adding points can never help. This is not a difficult proof:

Let A be a set of points, and let T be the set of all triangles whose vertices are drawn from A.

Let A' be any set of points that is a superset of A.

Let T' be the set of all triangles whose vertices are drawn from A'.

We can immediately observe that, since A is a subset of A', T is likewise a subset of T'.

Therefore, the smallest triangle in T' can never be larger than the smallest triangle in T, because the smallest triangle in T is a member of T'.

> I can think of a few other examples.

You can claim to, but you won't be telling the truth. This is a simple case of the obvious principle that if you're playing against an omniscient opponent, giving more options to them can't help you.

I misunderstood. when you said > Adding points to the set can only ever shrink the size of the smallest triangle that the set defines.

I thought you meant, adding points would shrink the size of the smallest triangle. Rereading the thread and the article, (I think you mean) The only possible effect (if there is any effect at all) of adding points is is to shrink the size of the smallest triangle.

I was thinking of a 10x10 square, and points at (0,0) (0,1) (1,1) - adding a point at 5,10 has no effect on the smallest triangle, but you could add a point at 10,10, and get a line, area zero.

Thanks for the thoughtful reply.

if there're only three points, how many triangles can you get from that? one. so the biggest triangle is the smallest. thought that was obvious

And yet still some point arrangements make that triangle size zero, others make the area 1/2 (assuming unit square). Most something in between. It's a problem similar to sphere packing, just not quite as close to practical application. My brain refuses to auto-resolve already at n=5. Is the obvious distribution (four corners, one in the center) the best according to size of the smallest triangle? I think it is, but no quick answers from me on that one, sorry.

I love this story, it reads like a description of academic arcadia: scientists who when the day's work of teaching is over don't Netflix'n'chill (or go maximise their share of administrative leakage) but gang up on odd mindbenders.

That "obvious" distribution is actually the worst, three points are in a line so have area of zero.

Oh, that line (well, one of those two lines), ouch! All that is left to debate is wether a non-solution with two size zero triangles can be considered worse than variations that have only one of those or not. But I'll better leave that to others (hopefully, for their sanity, that group of others is am empty set)

Reply on news.ycombinator.com