New answers tagged

0

Although your line of thought seems to be in right direction but the time complexity is not correct. Construct a BST on the points. Since the points are sorted then it will take O(n) time Constructing BST will take $O(nlogn)$ considering it is height balanced. Otherwise in the worst case it can be $O(n^2)$. So your total time complexity will be $O(nlogn)$...


2

If you really do want to test points for equality, then oerpli's solution is ideal. Any standard dictionary data structure will do the job. However, for completeness, if you need to match points within some small distance (e.g. maybe these are floating point and you're reading one of them from an ASCII file where you can't guarantee precision), then you ...


2

You should use a set data structure for your subset-list. This would allow querying if it contains a given point in constant time. Your function, as python-like pseudocode: def FilterPoints(master, subset): # take the list and convert it to a set ( O(|subset|) subset_set = set(subset) # iterate through master and and the points that are not in ...


1

This was first solved by Jacob and Brodal in 2002; there is a recent arXiv submission of that work, "Dynamic Planar Convex Hull".


5

The problem can be solved in time $\tilde{O}(n^{4/3})$, using several algorithms: Agarwal, Partitioning arrangements of lines II: Applications. Chazelle, Cutting hyperplanes for divide-and-conquer. Matoušek, Range searching with efficient hierarchical cuttings. There is an essentially matching lower bound due to Erickson, New lower bounds for Hopcroft's ...


Top 50 recent answers are included