2

How to merge two tangled convex hulls (like this) to form a Convex Hull using Graham's Scan or anyother algorithm in linear time?

emotionull
  • 595
  • 2
  • 8
  • 24
  • Such merge should result in another c-hull? – Anonymous Nov 17 '14 at 00:59
  • If you want a c-hull of the whole thing, run Graham's Scan over the union of the points. What is the question? – Scott Hunter Nov 17 '14 at 01:01
  • You could Also assign points of one Hull to faces of other Hull and "continue" process of quick-hull. – Anonymous Nov 17 '14 at 01:03
  • 1
    Do you have the polygons or just the points? If you have the polygons it can be done in `O(N + M)`. Otherwise, it's `O((N + m) log (N + M))`, though you could also use an output sensitive algorithm to improve the latter somewhat. Also, in the case of having the polygons, it means you can merge `K` convex hulls with a total of `P` points into a single convex hull in `O(P log K)` via `K-way merge`. – Nuclearman Nov 17 '14 at 21:44

1 Answers1

0

Basically, you use Andrew's modification of the Graham scan algorithm.

After the points are sorted in xy-order, the upper and lower hulls are computed in linear time. Since you already have the two convex hulls , the xy-sorting of the convex hull points will also take linear time (e.g., reverse the lower hulls and merge-sort four sorted lists).

Since the rest of the algorithm will take linear time, the overall runtime is linear as you requested.

Here is a reference to some short python code implementing Andrew's modification to Graham's scan. See also my answer here.

Iddo Hanniel
  • 1,636
  • 10
  • 18