Looking for Partinioning Algorithms allowing for Constraints

Question

What algorithms exist that partition the domain according to a black box evaluation function (possibly subject to some assumptions)?

Examples

Simple Example

To better exaplain we consider as our evaluation function the body mass index (BMI), calculated as $\mathit{mass} / \mathit{height}^2$ (for mass and height given in kilogram and meters respectively). We assume the domain to be $[30, 200] \times [1, 2.5] \subseteq \mathbb{R} \times \mathbb{R}$.

For given BMI thresholds $25$ and $30$ the goal is to partition the domain according to the thresholds. That is, for $\mathit{mass}\in [30, 200], \mathit{height}\in[1,2.5]$ I want the following three partitions: \begin{align} \{(\mathit{mass}, \mathit{height}) &\mid \mathit{mass} / \mathit{height}^2 < 25\} \\ \{(\mathit{mass}, \mathit{height}) &\mid 25 \leq \mathit{mass} / \mathit{height}^2 < 30\} \\ \{(\mathit{mass}, \mathit{height}) &\mid 30 \leq \mathit{mass} / \mathit{height}^2\} \end{align}

Complex Example

The following example sheds some light on the assumptions that might hold for the evaluation function. Note that I made this example up; I don't know anything about forest fires.

We wish to analyze through simulation how long it takes a forest fire to reach a town. As relevant parameters we consider

• wind speed,
• wind direction,
• humidity of last 30 days and
• distance to town.

Evaluation Function and Assumptions: The evaluation function measures the time until the forest fire reaches the village in the simulation. The simulation is complex, and it is treated mostly as a black box. However, we assume that the evaluation function is robust, i.e. small input changes result only in small output changes.

Goal: We wish to categorize the parameter space into the regions:

• town reached in less than $6$ hours,
• town reached in between $6$ and $12$ hours and
• town reached in more than $12$ hours.

My Thoughts

At first I thought that this looks like an optimization problem, but I could not find anything in this direction.

Edit 1: Added a second example with assumptions, helpful to analyze the domain.

Answer 1

If I understand what you're looking for correctly, it looks like you want to compute the contour lines of constant BMI and use those as boundaries to separate your domain?

A very simple algorithm for approximating this is the marching squares algorithm.

The general premise of the algorithm is you discretize your domain into a grid of rectangular cells and evaluate the function you want to find the contours of on that grid. Then for each cell, determine if the value of the function is larger or smaller than your desired contour.

Once you have this general array of true/false, you can use a look-up table of 4 neighboring cells to determine roughly how the contour looks in between those 4 cell centers. Note that you may have to do some additional work to disambiguate saddle points (see the Wikipedia article for more details).

This process is used a lot already for analyzing scientific data that most plotting libraries have it built-in, though as far as I know not many of these libraries actually give you the path(s) which approximates the contour boundaries.

Here's an example using Matplotlib to generate the contour plot:

from numpy import *
from matplotlib.pyplot import *

mass,height = meshgrid(linspace(30, 200, 400), linspace(1, 2.5, 400))

bmi = mass / height**2

contourf(mass, height, bmi, [25, 30], extend='both')
colorbar()
xlabel('mass')
ylabel('height')
tight_layout()

There are of course limitations to this algorithm, notably that if the resolution you choose for your grid is larger than any "island" contours, then those contours will not be found at all.