# Calculate the discrete set of points B which are in the convex hull of the set of points A

This problem is likely best described with the following picture:

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.

• although this question is upvoted and mathoverflow has smart people, you might get more informed answers at the scicomp stackexchange – guest May 8 '14 at 18:52

## 1 Answer

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.

• 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. – Brendan Annable May 8 '14 at 17:39
• 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. – Brendan Annable May 8 '14 at 18:37
• @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... – Joseph O'Rourke May 8 '14 at 18:48
• 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. – Brendan Annable May 8 '14 at 18:58
• @BrendanAnnable: I think, in fact, that is a slower algorithm. But about now the software will tell us to cease the private conversation. :-) – Joseph O'Rourke May 8 '14 at 19:22