Take a 1 meter by 1 meter square, and scatter a bunch of points inside. Every 3 of those points forms a triangle with those points as its vertices. Take the smallest one of those triangles and compute its area.
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.
Just to comment: something that tripped me up when first reading the problem statement is that I didn't realize degenerate triangles counted. Once you have 3 colinear points in your arrangement you're done for!
> 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.
There are sets of triangles and in each one there will be a smallest triangle by area. Now look at all of these possible sets for a given number of points. There‘s a value for the area that this smallest triangle cannot exceed. That’s the biggest smallest triangle. The researchers here showed that this value was so far overestimated.
Take a 1 meter by 1 meter square, and scatter a bunch of points inside. Every 3 of those points forms a triangle with those points as its vertices. Take the smallest one of those triangles and compute its area.
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.
Just to comment: something that tripped me up when first reading the problem statement is that I didn't realize degenerate triangles counted. Once you have 3 colinear points in your arrangement you're done for!
> 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.
4 replies →
The question is, how big is the smallest triangle, not how big is the biggest triangle.
9 replies →
There are sets of triangles and in each one there will be a smallest triangle by area. Now look at all of these possible sets for a given number of points. There‘s a value for the area that this smallest triangle cannot exceed. That’s the biggest smallest triangle. The researchers here showed that this value was so far overestimated.
The article explains it in laymen's terms.
I must not be a laymen then.