1
$\begingroup$

What is computational complexity for computing perimeter of a polygon of $n$ vertices? The polygon is not necessarily regular and can be convex or non-convex.

$\endgroup$
  • 1
    $\begingroup$ In what form are you given the polygon? e.g. this could be a list of vertices in order around the polygon. $\endgroup$ – Brian Borchers Apr 23 '16 at 18:56
  • $\begingroup$ @Brian The only given input is: 2D coordinates of n vertices of the polygon in a sequential order w.r.t either the clock-wise or the counter clock-wise direction. $\endgroup$ – user251385 Apr 24 '16 at 4:31
1
$\begingroup$

Either one way or the other, the polygon is composed of vertices and the links between vertices.

Typically this is expressed as an ordered sequence of vertices. In this case, you just sum up the consecutive vertex to vertex distances and this is $O(N)$. The main reason is that the single distance computation is $O(1)$:

$$ \lVert \mathbf{v}_i - \mathbf{v}_j \rVert = \sqrt{(\mathbf{v}^x_i-\mathbf{v}^x_j)^2+(\mathbf{v}^y_i-\mathbf{v}^y_j)^2} $$ and you simply perform a single pass over the vertices $$ P = \sum\limits_{i=2}^N \lVert \mathbf{v}_i - \mathbf{v}_{i-1} \rVert $$ where $P$ is the perimeter. For closed polygons, you just add another distance: $$ P_C = \sum\limits_{i=2}^N \big(\lVert \mathbf{v}_i - \mathbf{v}_{i-1} \rVert \big) +\lVert \mathbf{v}_1 - \mathbf{v}_{N} \rVert $$

If the polygon is presented as a vertex & edge list (similar to a graph), then you iterate over all the edges and once again sum up the edge lengths. You should take care of not adding the contributions multiple times. This can easily be done with the help of a hashtable, making the entire complexity to be $O(N)$, again.

$\endgroup$
  • $\begingroup$ The only given input is: 2D coordinates of n vertices of the polygon in a sequential order w.r.t either the clock-wise or the counter clock-wise direction. Can the computation of the distances as well as the sum of these computed distances be accomplished in O(n)? I thought the sum is O(n)..and was not sure about complexity of computing the sequential distances. $\endgroup$ – user251385 Apr 24 '16 at 4:32
  • $\begingroup$ Okay I added more detail to my answer. $\endgroup$ – Tolga Birdal Apr 24 '16 at 8:14
  • $\begingroup$ Great. One other final comment request: if this perimeter was computed p times then the complexity would be O(np)O(np)? Also, if it was computed O(log(1/ϵ))O(log(1/ϵ)) times instead would it be $O(n log(1/\epsilon))$ ? $\endgroup$ – user251385 Apr 24 '16 at 22:49
  • $\begingroup$ If you naively compute p times it is of course $pO(N)$. I don't really get what you by computing $O(log(1/ϵ))O(log(1/ϵ))$ times. I guess you could figure out the rest. $\endgroup$ – Tolga Birdal Apr 25 '16 at 0:00
  • $\begingroup$ Ok my bad I mistyped the complexity two times in a row. I meant "Great. One other final comment request: if this perimeter was computed p times then the complexity would be $O(np)$? Also, if it was computed $O(log(1/ϵ))$ times instead would it be $O(nlog(1/ϵ))$" But your answer gave me the hint and I can figure out now indeed :) $\endgroup$ – user251385 Apr 25 '16 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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