Do you know a good methodology to estimate the boundary between two sets? Here are the specifics of the problem:

enter image description here

I am studying a recursion defined as $$ 2(n+q) x_{n+2}= (r(n+q) +s)x_{n+1}+((2-r)(n+q)-s)x_n$$ with $x_0=0, x_1 = 1$. I am interested in identifying when $0 < \lim_{n\rightarrow\infty}|x_n| < 1$. More specifically, for which values of $(q, r, s)$ this is occurring. I actually solved this problem here, and the problem itself, even its solution, is irrelevant.

Let's pretend that we observe the points as in the above picture, let's pretend we don't even know how they were generated, and the goal here is to find the boundary between the red dots and the blue dots (red dots correspond to convergence, blue dots to no convergence.) I know the exact shape of the orange border, so this is a good example to benchmark boundary estimation techniques. But let's pretend that we don't know the exact boundary.

My question

What are the modern techniques used by statisticians to solve this problem?

Important notes

If the domain is convex, usually the convex hull is a good estimator. But what if it is not convex (in my example, it is barely convex, and in addition, non-bounded.) If the points were on a grid, there are plenty of techniques available, but here sample points are not on the grid. What about using density estimation techniques, assuming the points are uniformly distributed on some unknown domain to be estimated? Keep in mind that here, the domain is NOT bounded, so rather than a uniform density, one might look at the intensity of a 2-D or 3-D Poisson process on some unknown domain.

This is a actually 3-D problem. I only displayed one slice here (corresponding to $s=2$), but ideally, I am looking for a technique that works in 3-D. One could also treat this as a clustering problem, or better, a regression problem where the goal is to estimate the shape of the orange contour. The regression could be something like $f(q)=a_1 + b_2 r$ after some appropriate transformation $f$ that needs to be identified. Here $f(q) = \frac{1}{q+2}$ but you are not supposed to know it, the physics of my problem suggests that this is the correct transformation. How would you perform such a regression since most of the dots (far away from the border) must be discarded?


This is called a classification problem, ie to any $(r,q)\in R^2$ we want to assign a most likely label (namely red or blue). With a nonlinear boundary, some of the available methods are $k$-nearest neighbours, support vector machines, or Gaussian process regression (logit or probit typically).

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.