# Linear time algorithm to sort points of a simple polygon

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.

• 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? Feb 15, 2017 at 15:51
• See the update... but there's no proof of the statement, it's just... a statement. Feb 15, 2017 at 16:00
• Given the hypothesis however, I'm quite sure it can be done. Feb 15, 2017 at 16:03

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