0
$\begingroup$

In triangulating a simple polygon, using the concept of sweep line helper vertices etc, the very first step is sorting the vertices of such polygon. Apparently this very step can be done in $O(n)$ (where $n$ is the number of vertices). I'm trying to work out why... Assume there's no degenerate case (for any pair of points belonging to the polygon their $y$ coordinates are different). Because of such property a strict order exists $y_1<y_2<\ldots<y_n$, assume each point is stored in floating point $y_i = (e_i,m_i)$, I can't really see how to sort these points in linear time... could anyone give me an hint?

Source : Computational Geometry - Algorithm and application (DeBerg et all) chapter 3:

The claim is this

We now analyze the running time of the algorithm. Constructing the priority queue $\mathcal{Q}$ takes linear time...

Any kind of priority involves order relationships, so I assume some kind of ordering algorithm is used. Eventually the priority queue can be implemented using binary trees or heaps (basically these are the same thing) but It would still require $O(n \log n)$. I know ordering algorithms that run in linear time, however I don't think any of those can be applied in case of floating point numbers.

Improve this question
$\endgroup$
3
  • $\begingroup$ You say "Apparently this very step can be done in $O(n)$ (where $n$ is the number of vertices)." How do you know? What is your source? $\endgroup$
    – jbapple
    Commented Feb 15, 2017 at 15:51
  • $\begingroup$ See the update... but there's no proof of the statement, it's just... a statement. $\endgroup$
    – user8469759
    Commented Feb 15, 2017 at 16:00
  • $\begingroup$ Given the hypothesis however, I'm quite sure it can be done. $\endgroup$
    – user8469759
    Commented Feb 15, 2017 at 16:03

1 Answer 1

Reset to default
2
$\begingroup$

You ask:

the very first step is sorting the vertices of such polygon. Apparently this very step can be done in $O(n)$

but the book says

We now analyze the running time of the algorithm. Constructing the priority queue QQ takes linear time...

Constructing a priority queue does not take as much time as sorting. Priority queues can be constructed in linear time. The most famous algorithm for doing this is called "heapify".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.