1
$\begingroup$

I've come to an interesting problem. Let's have a 2D scalar function F and make some assumptions on it:

  • it has compact support (region where it is defined and non-zero)
  • its support consists of at most one continuous region (not several parts)
  • its support is continuous
  • at the border of the support there there might be discontinuities (steep cliffs) of the function F
  • the support might not be convex
  • the support is subset of a finite rectangle A parametrizable as [0;1]^2 topologically equavalent to cylinder without caps (left and right sides are wrapped around)

An example of such function might be an analogy to 2D box function where the support is hexagon-shaped, star-shaped or crescent-shaped.

We can also work with the characteristic function X of the F's support (which indicates true iff the point is within the support).

The problem is to find an axis-oriented 2D bounding box (BB) of the support - either exact or approximate (slightly larger). The bounding box must contain the whole region and if possible should not miss any part of it. One goal is to make the bounding box embrace the support as tightly as possible. Second goal is to make the computation as fast as possible, even at the cost of geting just an slightly larger approximate bounding box.

Also the computation will be performed many times in succession on functions of very similar support, just moving around and slightly changing their shape.

I've thought about the possible solutions to the problem, but still haven't found a solution which would be elegant and robust. The possibilities are:

(1)

  • sample the rectangle A with some random points
  • mark each point with the characteristic function X as being either inside or outside the support
  • sort the X and Y coordinates of the sampled points
  • take the maximum outside X less or equal than the minimum inside X -> left BB side
  • take the minumum outside X greater or equal than the maximum inside X -> right BB side
  • (...and analogously for Y)

I'm not sure if this algorithm can guarantee that no parts of the support will be missed. It would probably converge to the right BB, but from the inside, not from outside.

We could always extend the computed BB by some percent, but it seems a bit ugly to me.

(2) To save generating of some random points we might incrementally build the BB from inside and not generate any more random points inside the BB as their information is useless (they can't extend the BB).

(3)

  • find a "seed" which is inside the support
    • eg. generate some random points within rectangle A
  • go linearly or by binary searching in one direction to find the boundary of the support
  • trace the boundary around and find minima and maxima in each coordinate

As the support might be non-convex the might be more than one extreme which would touch the bounding box.

(4) If we assume that the support do not contain any slim parts going outside less than some size we could divide the rectangle into a raster and find the rasterized border eg. with contour tracing. The possible error caused by rasterization could be compensated by enlarging the resulting BB by a pixel or so.

This wouldn't be much efficient for larger supports.

(5) When computing BB's of several similar functions in a sequence as the initial seed could be used the barycenter of the previous resulting BB, possibly shifted by gradient of this quantity.

What do you think about such a problem? Does anybody have an experience with something similar or could recommend a particular technique useful in this context. Any help is appreciated! Thank you very much!

$\endgroup$
  • 3
    $\begingroup$ If you're only give access to F as a black box, I don't see how any sampling-based strategy will work, since I can always create a measure zero (or exponentially small) spike that controls the bounding box. I think you need more structure on F to be able to solve this. $\endgroup$ – Suresh Venkat Jun 17 '11 at 17:50

Your Answer

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

Browse other questions tagged or ask your own question.