2
$\begingroup$

I am looking for an efficient algorithm that can partition an area $B \subset \mathbb{R}^2$ into disjoint subsets $B = \bigoplus_i U_i$ such that a test function is constant on each of the subsets, $f \vert_{U_i} = \mathrm{const.}$

For example, consider the following partitioning:

Partitioning

The indicated numbers are the return values of the test function in each cell. I want to recover the partitioning, given area error bounds, with the least number of function calls.

My current approach uses a recursive grid-based method that tests at each vertex of an intial $n \times n$ grid. If not all vertices of a grid cell have the same function value, the cell is subdivided and the process repeats. This needs many subdivisions, and the initial grid must be "fine enough".

I am curious if a specialized approach exists, and if there is a common name for this problem.

$\endgroup$
  • 1
    $\begingroup$ Are the regions convex? IOW, if f(p) = f(q) for a pair of points p and q, is it guaranteed that f(r) = f(p) for all r = ap + (1-a)q with 0 <= a <= 1? $\endgroup$ – j_random_hacker May 20 '14 at 7:25
  • $\begingroup$ No, I'm sorry for the rather misleading example image. In my applications, the regions will mostly even have "spikes", but if there's an answer for convex regions, I'm still curious. $\endgroup$ – user16858 May 20 '14 at 8:08
  • 1
    $\begingroup$ I see. The advantage of convexity would simply be that if you have 3 or more non-collinear points with the same function values, it's never necessary to test any further points within the polygon that they define, since they must necessarily have the same function value. Without this, AFAICT the best you can do is grid search -- and without other guarantees (e.g. on the minimum diameter of any region or "spike") it's impossible to even know how fine you need to go, since between any two searched points having equal value, there might be a region or "spike" of a different value. $\endgroup$ – j_random_hacker May 20 '14 at 9:19
0
$\begingroup$

The discrete version of your problem has a close resemblance with the classical Clustering problem. In Clustering given a finite set of points you have to divide the set such that points belong to a partition (cluster) iff they have similar properties.

We consider the continuous version, i.e, your problem. Let $2\epsilon < 1$ is error bound. And, we have a bounding box of size $n*n$ which we would like to partition based on functional values.

We divide the bounding box into $n/\epsilon*n/\epsilon$ grid cells, each cell has $\epsilon$ length side. Here we apply bottom up approach where the consecutive cells having same functional values are merged together. The partitioning algorithm is as follows.

i) For each grid cell $c$, compute function values in its four corner points. Let $x$ be the function value occurring most frequently among those four values (in case of tie choose one arbitrarily). Assign $x$ as a label to $c$.

ii) Start with the left and topmost grid cell. Iterate over cells from top to bottom and in a single row from left to right. In each cell $c$ if the cell on left and above (if exists) have same labels add $c$ to the cluster (partition) correspond to those cells (merging). Else if one of the left or above cell has same label add $c$ to the cluster (partition) of that cell. Otherwise start a new cluster with $c$.

You can see that the error may occur in boundary regions (between two partitions) of the partitioning and the merging procedure will give correct partitions. But, as the boundary consists of $\epsilon$ side length boxes the error is within tolerance limit.

Time complexity is $O((\frac{n}{\epsilon})^2)$.

$\endgroup$
0
$\begingroup$

As stated, this problem is not solvable. Your problem is analogous to: "given the sequence 1,3,5,7,9, what is the next number in the sequence?" The answer that puzzle is: "without further information, it could be anything (you can always find a degree-5 polynomial that will make the answer anything you want)".

You have not given us any restrictions on the test function, nor have you given us any regularity conditions on it. If we don't know anything about it, then as j_random_hacker says, your problem is not solvable: if you query the test function $n$ times and construct a partitioning that is consistent with the responses from the test function, an adversary can always come up with a $n+1$th query and a response to that query that demonstrates that your partitioning is wrong. Thus, no finite number of queries ever suffices, if you don't narrow down the set or structure of possible test functions in some way.

To make this solvable, you need some structure on the set of possible test functions: say, that test functions are known to be convex, or something.

$\endgroup$
  • $\begingroup$ That is correct, of course. In the case I'm interested in, there are no guarantees about the function, except that it does not change "below a given length scale". So there are no infinitely fine isles of differing values. The only problematic features are the boundaries of the regions, which should be resolved up to some error bound. $\endgroup$ – user16858 May 21 '14 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy