-1

I've researched several algorithms for determining whether a point lies in a convex hull, but I can't seem to find any algorithm which can do the trick in O(logn) time, nor can I come up with one myself.Let a[] be an array containing the vertices of the convex hull, can I pre-process this array in anyway, to make it possible to check if a new point lies inside the convex hull in O(logn) time.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
Andrew Brick
  • 276
  • 2
  • 4
  • 18
  • You might also want to ask this question on the Mathematics site. It sounds like you are more interested in the algorithm itself rather than the implementation. – Tim Biegeleisen Mar 02 '15 at 02:31

1 Answers1

1

Looks like you can.

  1. Sort vertices in a[] by polar angle relative to one of vertices (call it A). O(N log N), like convex hull computation.
  2. Read point, determine its polar angle. O(1)
  3. Find two neighbor vertices, one of them should have polar angle less than point from step 2, and other should have angle bigger (B and C). O(log N), binary search
  4. Then simple geometry: draw the triangle between points from A, B, C and check if point from step 2 lies inside. O(1)
Everv0id
  • 1,862
  • 3
  • 25
  • 47
  • what are pt. 1, 2 and 3 in this case, is pt. 1 the point being tested, and pt. 2 and 3 are nrighbouring points satisfying the condition in step 3? – Andrew Brick Mar 02 '15 at 02:48
  • Also can you explain how step 3 is done in O(logn) time please – Andrew Brick Mar 02 '15 at 02:49
  • no, sorry for my abbreviations :) pt.1 is item 1 (sort), pt.2 is item 2 (read point), etc. – Everv0id Mar 02 '15 at 02:50
  • oh I see, but it's still possible for a point to not lie on the line connecting the neighbouring points and still be in the convex hull – Andrew Brick Mar 02 '15 at 02:53
  • Seems like i misunderstood your problem. Do you mean that the point can lie *inside* convex hull? – Everv0id Mar 02 '15 at 02:55
  • yes, I'm checking to see if it lies inside the convex hull, not just on an edge of the convex hull – Andrew Brick Mar 02 '15 at 03:00
  • in step 4, are you checking to see if the triangle is contained within the convex set, but I don't think this can be done in O(1) time, is there a way to do it in O(logn) time – Andrew Brick Mar 02 '15 at 03:03
  • Nope. In step four we already have points A, B, C. If the point we check lies outside of triangle ABC, that means it lies outside the whole convex hull. – Everv0id Mar 02 '15 at 03:05
  • sorry about the huge stack of questions, but I have just one more to ask. The polar angle of a vertex is the angle the vector going from the origin to the vertex makes with the x-axis, but I've never seen the polar angle of a vertex relative to another vertex(point A in our case). Would this be the angle between the vectors from the origin to the point and the vector from the origin to the point A. – Andrew Brick Mar 02 '15 at 03:14
  • "Formally, the point (x1, y1) is less than the point (x2, y2) if and only if the slope (y1 − y0) / (x1 − x0) is less than the slope (y2 − y0) / (x2 − x0)." from there: http://coursera.cs.princeton.edu/algs4/assignments/collinear.html – Everv0id Mar 02 '15 at 03:19
  • You can easily do it in Log(h) by using my algorithm using intermediate quadrant result. See: https://www.codeproject.com/Articles/775753/A-Convex-Hull-Algorithm-and-its-implementation-in and/or (more recent) : https://www.codeproject.com/Articles/1210225/Fast-and-improved-D-Convex-Hull-algorithm-and-its – Eric Ouellet Nov 22 '17 at 15:50