3
$\begingroup$

This problem is likely best described with the following picture:

Set $A$ shown in blue, set $B$ shown in red, bounding box shown with black lines

Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the convex hull of set $A$, producing set $B$ (shown in red). Note that it is not necessarily required to calculate the convex hull itself, although it may be advantageous to do so.

I have been able to achieve this by testing whether each point within the bounding box (shown in black) is linearly separable from the entire set $A$ (using linear programming). However this is very slow when set A is large and in higher dimensions and I feel like testing each point is not necessary.

Preferably I'd like some advice on where to look for optimizing my search for points. Maybe fit a rectangle inside to avoid testing all points? I'm just looking for ideas or other solved methods.

For my application I need to extend this to 3D but I find solving these problems in 2D and generalizing much easier.

$\endgroup$
1
  • $\begingroup$ although this question is upvoted and mathoverflow has smart people, you might get more informed answers at the scicomp stackexchange $\endgroup$
    – guest
    May 8, 2014 at 18:52

1 Answer 1

6
$\begingroup$

Let $n$ be the number of blue points $A$. You can compute the convex hull of $A$ in $O(n \log n)$ time in both 2D and 3D. Code to achieve that time complexity in 3D is quite difficult, so usually the much simpler $O(n^2)$ algorithms are used in 3D. Code is available from a number of sources, including my own.

There are various strategies to avoid listing each red point $B$ (which would require time proportional to $|B|$). The simplest is to record the start and end cell in each $x$-axis-parallel lattice-segment inside the hull, which could be accomplished by intersecting the hull with each $x$-lattice-line.

You could also find the largest enclosed axis-parallel rectangle in the hull, and record that subset of $B$ in bulk. But then you'd need to supplement this rectangle with what lies outside of it but still in the hull, which may reduce to the lattice-segments approach above.

$\endgroup$
5
  • $\begingroup$ Do I need to calculate the convex hull? All I need to do is test if the points are within the convex hull. I'm not sure which way is faster yet though. I do need the set of points in $B$ at the end of the day. $\endgroup$ May 8, 2014 at 17:39
  • $\begingroup$ Thinking about this further, if I were only to test a single point, it is likely faster not to compute the convex hull, but given your suggestion, at first glance it would speeds things up significantly. $\endgroup$ May 8, 2014 at 18:37
  • $\begingroup$ @BrendanAnnable: I don't know how you could determine if a single point is in the hull without knowing the hull itself, at least implicitly. But perhaps I misunderstand your intent... $\endgroup$ May 8, 2014 at 18:48
  • $\begingroup$ See this answer here stackoverflow.com/a/11731437/868679 - simply testing whether a hyperplane exists between a given point and the pointcloud will determine whether the point is within the convex hull or not (via linear programming/SVM or any other classification technique). My intentions were to maximize on this fact and potentially have a faster algorithm. $\endgroup$ May 8, 2014 at 18:58
  • $\begingroup$ @BrendanAnnable: I think, in fact, that is a slower algorithm. But about now the software will tell us to cease the private conversation. :-) $\endgroup$ May 8, 2014 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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