Solved

Convex-Hull (2D) incremental construction

Posted on 2006-11-17
9
676 Views
Last Modified: 2012-06-27
Hi,

Is there an incremental algorithm for convex-hull (in the plane) construction in O(nlogn) ?
That is, we add the points one by one, and each step takes O(logn) time (not amortized, but exactly).

Thanks!!
0
Comment
Question by:slavikn
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 3
  • 2
9 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 17969091
yes
0
 
LVL 84

Expert Comment

by:ozo
ID: 17969155
Sorry, that's amortized.
I don't think it can be exactly because you may have to remove O(n) points from the hull when you add a new point
0
 
LVL 1

Author Comment

by:slavikn
ID: 17970979
I saw an amortized one, that uses lower and upper binary trees.
Is there an easier algorithm?
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 18

Expert Comment

by:Jose Parrot
ID: 18042654
Hi, slavikn ,

To achieve O(n log n) time, a really good approach is to divide the problem in two parts, upper and lower parts of the convex hull.
By finding the leftmost and the rightmost vertices of the given set, we have the ending vertices of each part.
To find such vertices, we use a O(n log n) sorting algorithm, say, merge-sort.
The finding of each vertice is actually O(n). The final result is O(n log n) + O(n) = O(n log n).

Below is an algorithm for the upper part of the convex hull.

CH(P)
Input: set P of points
Output: a list of convex hull points in clockwise order
{
   UpperList = empty set
   Sort points by x-coord, s.t. p1.x < p2.x < ... <pn.x
   Add point p1 to UpperList
   Add point p2 to UpperList
   for i=3,n
   {
      append pi to UpperList
      {
          while number of points in UpperList > 2
                              and
          last 3 points in UpperList don't make a RIGHT turn
          {
              delete the middle of last 3 points from UpperList
          }
      }
   }
}

Sort points ... is O(n log n)
Add points is linear: O(1)
The "while" loop is executed at least once, each time the "for" loop is executed. So O(n).
Each additional execution of the "while" loop results in exactly one point deletion.
So, again O(n), because we have n points and each one can deleted just once.
Then final time is O(n log n) + O(1) + O(n) + O(n), resulting in O(n log n).

For lower part is similar, except for direction which is from right to left.
This algorith is easy to implement, I don't know about an easer algorithm for convex hull.
Hope it helps.

Jose
0
 
LVL 1

Author Comment

by:slavikn
ID: 18047665
Thanks for the detailed explanation JoseParrot.
However, the algorithm I asked for was supposed to be pure incremental, that is without the O(nlogn) sorting in advance.
Eventually I've found a solution (well, nearly, as each step is O(logn) only in amortized...). It's here: http://ww3.algorithmdesign.net/handouts/IncrementalHull.pdf
0
 
LVL 1

Author Comment

by:slavikn
ID: 18047677
By the way, I am still looking for a "pure" incremental algorithm with exact complexity of O(logn) in each step (not amortized). A very simple initialization is allowed.
0
 
LVL 18

Accepted Solution

by:
Jose Parrot earned 80 total points
ID: 18071034
Well, as far I know, there are several algorithms, with amortized times O(log n log log log n for insertion and  O(log n log log n)  for deletion); the naive O(n^2); the classic O(n), other for O(log^2 n); other with very small gain on O(log log n).

Riko Jacob's PhD thesis, Dynamic Planar Convex Hull of University of Aarhus,  Denmark, claims O(log n) worst case. I didn't accessed this paper.

As you are looking for "exact" O(log n), it seems to be Theta(log n). In such way,  parallel algorithm could be your answer. You may want take a look at
http://www.cse.buffalo.edu/pub/WWW/faculty/miller/Papers/IEEETC88a.html

Jose

0
 
LVL 18

Expert Comment

by:Jose Parrot
ID: 18335216
Hi, slavikn,

The answer to
"Is there an incremental algorithm for convex-hull (in the plane)
 construction in O(nlogn) ?"
is: YES.

Below some of such algorithms:

ALGORITHM 1
Scan, by Graham, 1972
Starting from leftmost point P1, the algorithm has 2 steps:
1) Sorting angles from P1 to P2 until Pn, by Divide and Conquer: O(n log n)
2) Discovering next point, by Greedy approach (point by point): O(n).
Result is: O(n log n) + O(n) --> O(n log n)

ALGORITHM 2
Divide-and-Conquer, by Preparata and Hong, 1977

OTHERS variants, after that:
Monotone Chain, by Andrew, 1979
Incremental, by Kallay, 1984
Marriage-before-Conquest, by Kirkpatrick & Seidel, 1986

Kallay's incremental algorithm description follows. Rather than determine the hull by looking at the whole set of points at once, as in 1 and 2, Kallay's looks at a subset of the points and then increase the subset until it was the entire set. The minimum subset, of course, is a triangle. The points aren't sorted, but the hull construction complexity is O(n log n).

For a pretty complete article, you may want take a look at
http://geometryalgorithms.com/Archive/algorithm_0109/algorithm_0109.htm
With details, pseudo codes and C code.

Hope slavikn is still around and this answer helps...

Jose
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

732 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question