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: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.
Partition area using test function
algorithms;computational geometry;partitions
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)$.