Algorithm to compute the area of a convex set in 2 dimensions

Solution 1:

If all you have is a membership oracle, you can run the marching squares algorithm on it to extract a reasonably accurate polygonal approximation, and then calculate the area of that using any area-calculating algorithm you can find online. The good thing about the marching squares is that I think there are implementations whose outputs are Delaunay triangulations.

It is difficult to evaluate the complexity of such a process with relation to $c$ and $\epsilon$, but all I can say is that it depends on the step of the grid you use to run the marching squares algorithm (since the area-computing algorithm doesn't depend on those variables). It may be even harder than that, since for example a square only needs a super rough estimate but something that looks like a piecewise segment (ie very thin) would need an extremely low error range.

Solution 2:

We agreed in comments that we should know a point of $K$. (Let it be the origin.) But it is not enough to solve the problem. If $K$ is extremely long and superthin, it is really hard to find any other point of $K$. (For example $K$ may be a rectangle $0.000\,001\sqrt{\epsilon} \times 1\,000\,000\,000\sqrt{\epsilon}$, rotated by some angle.) Therefore we need to have at least two points.

If these points are too close to each other then the problem obviously remains. So we need to have at least two “not-too-close” points. If area of $K$ is at least $\epsilon$ then there are two points at distance at least $2\sqrt{\frac{\epsilon}{\pi}}$. (And otherwise answer $0$ would be acceptable.) We can't require two points with greater distance, because $K$ may be a circle of radius $\sqrt{\frac{\epsilon}{\pi}}$.

Ok, suppose we have two points at distance at least $d = 2\sqrt{\frac{\epsilon}{\pi}}$. And $K$ is the same extremely long and superthin rectangle. We still have no evident way to find an approximation of area of $K$. Really an intersection of $K$ and a line $\ell$ containing given points may have as small length as $d$. On the other hand an intersection of $K$ and a line that is perpendicular to $\ell$ may be almost as short as width of $K$. Therefore we again need to find the direction of superthin $K$ to get a good approximation of the area of $K$. So we need either some significant number of operations (I will estimate later) to find this direction or three points that are vertices of a triangle of big enough area.

Solution 3:

One can answer the original question, and possibly better understand the costs involved, by splitting it into two parts.

The first is: how do we find any one point of a convex set $K$ in the unit disk given a membership oracle, and knowing that the convex set has area at least $\epsilon$ (otherwise, $\epsilon$ is an $\epsilon$-additive approximation of the area)? It's easy to see that taking $O\left(\frac{1}{\epsilon}\log\frac{1}{\epsilon}\right)$ samples uniformly and independently at random and querying the oracle for each yields a point with probability at least $1-\epsilon$. It's harder to prove that any algorithm requires at least $\Omega\left(\frac{1}{\epsilon}\log\frac{1}{\epsilon}\right)$ queries to guarantee the same probability, but I believe it's true ($\Omega(\frac{1}{\epsilon})$ is, of course, trivial).

The second part is: how can we find an (additive) $\epsilon$-approximation of the area of a convex set $K$ in the unit disk given a membership oracle and a generic point belonging to $K$? This is slightly more complicated, but essentially can be carried out by finding two convex polygons $P_1,\dots,P_n$ and $P'_1,\dots,P'_n$, the former containing and latter contained within $K$ and such that the distance between $P_i$ and $P'_i$ is sufficiently small. I believe the cost can be pushed down to $O(\epsilon^{-2/5})$ for a Montecarlo algorithm with, say, $2/3$ probability of success. It's easy to see that one needs always at least $\Omega(\epsilon^{-1/3})$ queries, taking a regular $2n$-agon inscribed in the unit circle, and considering the $n$ triangles each formed by $2$ consecutive even-indexed vertices and the odd-indexed vertex between them. Each such triangle has base $\Theta(n^{-1})$ and height $\Theta(n^{-2})$, and each can be independently "snipped" without compromising the convexity of polygon; so that for some sufficiently small $n=\Theta(\epsilon^{-1/3})$ the area of each triangle exceeds $\epsilon$, and one must check with a distinct query the presence or absence of each triangle (save possibly one) to determine the area of the polygon within an additive factor $\epsilon$.

For both parts, it's not difficult to prove that the upper bound on the number of queries is also asymptotically an upper bound on the number of all other operations involved.