Given a set of points S, and a point p determine whether there exist a half-plane L such that L contains p but does not contain any other point from S

user_17543723 0
Viewed 50

Given a set of points S, and a point p, determine whether there exist a half-plane L such that L contains p, but does not contain any other point from S.

My solution:

find the CH(S) - o(nlogn).

check if p is inside CH(S) - o(n).

return true iff p is inside CH(S).

Total time complexity - o(nlogn).

Is there a more efficient algorithm?

computational-geometry algorithm
1 Answers

Assuming from your proposed algorithm that we're considering a Euclidean space with three dimensions (or even a fixed number of dimensions), yes, there's a linear-time algorithm by formulating the problem as a linear program and solving it with Megiddo's algorithm.

user_21446690
Related