

Revision History 

I didn't submit anything this time because of lack of time (hey, I'm finally upgrading to Linux after 15 years of being trapped in Windows!). Anyway, I want to share my unfinished approach as it has an idea I haven't seen posted by anyone yet.
In the first phase, I generate a lot (50K) of convex polygons according to the test generator (but I skip all those few polygons that would take a long time to generate). Then I search for a query point that would return false/true for ~50% of the sample polygons. After the query, all the sample polygons that are not consistent with the feedback are removed; if the number of sample polygons is lower than 1K (which happens very quickly as we're removing one half on each query) then new polygons are generated by randomly "mutating" the existing samples such that they are still concave and consistent with the feedbacks.
The second phase starts once the "diversity" of the samples drops below a certain threshold value (as measured by the std. dev. of the areas of the samples). This phase is very similar to what have been posted already: find the query point that maximizes {area discarded if false, area accepted if true}. As radeye has already pointed out, I also found that this binary search was suboptimal, in the sense that the entropy gain was lower than 1bit per query.
The third phase is the one that I didn't have the time to implement; it started once all queries were exhausted and would consisted in randomly generating (as the time limit allowed) valid concave polygons between the minimum convex hull and the outside points, and returning the average area as the result.
I found that the first phase was nearoptimal (before diversity dropped), and much better than random sampling of points. For example, it found on average (over 1000 cases) the first "inside point" using ~2 queries, which is indeed the expected value for 1bit entropy queries (on the other hand, random sampling used more than twice as much queries to find each of the first 3 inside points).
@jdmetz: nice idea to use a genetic algorithm to tune your estimation parameters (that's commented on the source). Do you have a generic framework for doing this, or is it an adhoc solution? (edit  why I've the feeling I've asked this before???)
edit  convex => concave... d'oh!


I didn't submit anything this time because of lack of time (hey, I'm finally upgrading to Linux after 15 years of being trapped in Windows!). Anyway, I want to share my unfinished approach as it has an idea I haven't seen posted by anyone yet.
In the first phase, I generate a lot (50K) of convex polygons according to the test generator (but I skip all those few polygons that would take a long time to generate). Then I search for a query point that would return false/true for ~50% of the sample polygons. After the query, all the sample polygons that are not consistent with the feedback are removed; if the number of sample polygons is lower than 1K (which happens very quickly as we're removing one half on each query) then new polygons are generated by randomly "mutating" the existing samples such that they are still concave and consistent with the feedbacks.
The second phase starts once the "diversity" of the samples drops below a certain threshold value (as measured by the std. dev. of the areas of the samples). This phase is very similar to what have been posted already: find the query point that maximizes {area discarded if false, area accepted if true}. As radeye has already pointed out, I also found that this binary search was suboptimal, in the sense that the entropy gain was lower than 1bit per query.
The third phase is the one that I didn't have the time to implement; it started once all queries were exhausted and would consisted in randomly generating (as the time limit allowed) valid concave polygons between the minimum convex hull and the outside points, and returning the average area as the result.
I found that the first phase was nearoptimal (before diversity dropped), and much better than random sampling of points. For example, it found on average (over 1000 cases) the first "inside point" using ~2 queries, which is indeed the expected value for 1bit entropy queries (on the other hand, random sampling used more than twice as much queries to find each of the first 3 inside points).
@jdmetz: nice idea to use a genetic algorithm to tune your estimation parameters (that's commented on the source). Do you have a generic framework for doing this, or is it an adhoc solution?
edit  convex => concave... d'oh!


I didn't submit anything this time because of lack of time (hey, I'm finally upgrading to Linux after 15 years of being trapped in Windows!). Anyway, I want to share my unfinished approach as it has an idea I haven't seen posted by anyone yet.
In the first phase, I generate a lot (50K) of convex polygons according to the test generator (but I skip all those few polygons that would take a long time to generate). Then I search for a query point that would return false/true for ~50% of the sample polygons. After the query, all the sample polygons that are not consistent with the feedback are removed; if the number of sample polygons is lower than 1K (which happens very quickly as we're removing one half on each query) then new polygons are generated by randomly "mutating" the existing samples such that they are still concave and consistent with the feedbacks.
The second phase starts once the "diversity" of the samples drops below a certain threshold value (as measured by the std. dev. of the areas of the samples). This phase is very similar to what have been posted already: find the query point that maximizes {area discarded if false, area accepted if true}. As radeye has already pointed out, I also found that this binary search was suboptimal, in the sense that the entropy gain was lower than 1bit per query.
The third phase is the one that I didn't have the time to implement; it started once all queries were exhausted and would consisted in randomly generating (as the time limit allowed) valid concave polygons between the minimum convex hull and the outside points, and returning the average area as the result.
I found that the first phase was nearoptimal (before diversity dropped), and much better than random sampling of points. For example, it found on average (over 1000 cases) the first "inside point" using ~2 queries, which is indeed the expected value for 1bit entropy queries (on the other hand, random sampling used more than twice as much queries to find each of the first 3 inside points).
@jdmetz: nice idea to use a genetic algorithm to tune your estimation parameters (that's commented on the source). Do you have a generic framework for doing this, or is it an adhoc solution?


I didn't submit anything this time because of lack of time (hey, I'm finally upgrading to Linux after 15 years of being trapped in Windows!). Anyway, I want to share my unfinished approach as it has an idea I haven't seen posted by anyone yet.
In the first phase, I generate a lot (50K) of convex polygons according to the test generator (but I skip all those few polygons that would take a long time to generate). Then I search for a query point that would return false/true for ~50% of the sample polygons. After the query, all the sample polygons that are not consistent with the feedback are removed; if the number of sample polygons is lower than 1K (which happens very quickly as we're removing one half on each query) then new polygons are generated by randomly "mutating" the existing samples such that they are still concave and consistent with the feedbacks.
The second phase starts once the "diversity" of the samples dropped below a certain threshold value (as measured by the std. dev. of the areas of the samples). This phase is very similar to what have been posted already: find the query point that maximizes {area discarded if false, area accepted if true}. As radeye has already pointed out, I also found that this binary search was suboptimal, in the sense that the entropy gain was lower than 1bit per query.
The third phase is the one I didn't have the time to implement; it started once all queries were exhausted and would consisted in randomly generating (as the time limit allowed) valid concave polygons between the minimum convex hull and the outside points, and returning the average area as the result.
I found that the first phase was nearoptimal (before diversity dropped), and much better than random sampling of points. For example, it found on average (over 1000 cases) the first "inside point" using ~2 queries, which is indeed the expected value for 1bit entropy queries (on the other hand, random sampling used more than twice as much queries to find each of the first 3 inside points).
@jdmetz: nice idea to use a genetic algorithm to tune your estimation parameters (that's commented on the source). Do you have a generic framework for doing this, or is it an adhoc solution?

