# 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

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