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.
$\begingroup$
$\endgroup$
2
-
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 BorchersApr 23, 2016 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$– user251385Apr 24, 2016 at 4:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
$\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$ Apr 24, 2016 at 4:32
-
$\begingroup$ Okay I added more detail to my answer. $\endgroup$ Apr 24, 2016 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$ Apr 24, 2016 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$ Apr 25, 2016 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$ Apr 25, 2016 at 0:23