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.

Improve this question
$\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
    Commented May 8, 2014 at 18:52

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Brendan Annable
    Commented 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$
    – Brendan Annable
    Commented 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$
    – Joseph O'Rourke
    Commented 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$
    – Brendan Annable
    Commented 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$
    – Joseph O'Rourke
    Commented May 8, 2014 at 19:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .