Regular N-Gon Algorithm and Big O

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

daydalus
Posts: 76
Joined: Thu Aug 30, 2007 4:05 pm UTC

Regular N-Gon Algorithm and Big O

Postby daydalus » Thu Jun 19, 2008 4:41 pm UTC

My company started doing some algorithm challenges for fun.

First Question: Given n points (x, y coordinates), how will you determine they form a regular n-gon?
Required: provide an algorithm to generate a yes/no answer, provide the time order of calculation of your algorithm, code it. Provide all of these.

Here's the (psuedocode) of my solution. I'm not sure I did the Big O correctly, any comments are appreciated:

Spoiler:
Because points of a Regular N-Gon lies along the circumference of a circle, we first find the midpoint. Then calculate the expected spoke length and angle between adjacent spokes. Sort the list so the points lie along the circle's circumference and check each spoke. If any spokes fail, return false, otherwise true.

1. Traverse the list of points to determine bounds (small x, small y, big x, big y). O(n)
2. Generate midpoint from bounds. O(1)
3. Split list into two groups. Those y>midpoint.y and y<midpoint.y. O(n)
4. Sort the two lists. The "top" list with ascending X. The bottom list with descending x. O(n log n).
5. Generate expected spoke length (distance point n -> midpoint), angle (atan2). O(1)
6. Traverse the two lists, checking angle and length to match expected spoke angle and length. O(n)

O(n) + O(1) + O(n) + O(n log n) + O(n) + O(1) + O(n) = O(nlogn)

I'm not sure this is right. Is the distance formula, dot product, cross product, atan2 O(1) operations?

User avatar
Xanthir
My HERO!!!
Posts: 5425
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Regular N-Gon Algorithm and Big O

Postby Xanthir » Thu Jun 19, 2008 5:02 pm UTC

Distance formula can be treated as O(1) for reasonable inputs, though it's really O(n2) in typical implementations. Same with dot and cross product. Atan can easily be O(1) - if anyone challenges you, produce a lookup table. Preprocessing of that nature doesn't count. ^_^

Specific criticisms:
Spoiler:
Note: Your step 1 is false. You cannot accurately determine midpoint merely from bounds. You'll have to average all the x-values and y-values. Not a significant change, obviously.

Your steps 3 and 4 aren't optimal, as you don't actually need a sort. A regular n-gon will have its spokes separated by identical angles, and possibly be rotated by a fixed amount. Once you find the angle of *one* spoke, you know the rotation offset, and can immediately calculate whether each other spoke points in the correct direction without having to take them in order.

There *would* be the possibility of two points lying on top of one another (thus passing the angle test but still not forming an ngon), but that possibility is eliminated by the spoke-length test if you actually calculate the center of mass of the points (as such a situation would bias the center of mass toward the repeated point and produce differing spoke lengths).

Since we've eliminated the sort and are left with only a few naive list traversals with O(1) operations, the final big O should be O(n).


My algorithm:
Spoiler:
1) Traverse the list, summing up x-values and y-values, to determine center of mass of the points.
2) Traverse the list, calculating the distance of each point from the CoM. Fail if any are different.
3) Traverse the list, calculating angle each point makes with the CoM. Each angle should be Xn+Y, where X is given by the number of points and Y is an offset calculable from the first point. Fail if any are wrong.
4) If no failures have been encountered yet, pass the pointset.

Step 1 uses addition and division, both O(1) operations.
Step 2 uses the distance formula, which involves squaring and rooting. Both can be considered O(1) for reasonably-sized numbers.
Step 3 uses atan, which can be O(1) for sure if lookup tables are allowed, and can possibly be considered O(1) otherwise.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Regular N-Gon Algorithm and Big O

Postby jaap » Thu Jun 19, 2008 5:16 pm UTC

Xanthir wrote:My algorithm:
Spoiler:
1) Traverse the list, summing up x-values and y-values, to determine center of mass of the points.
2) Traverse the list, calculating the distance of each point from the CoM. Fail if any are different.
3) Traverse the list, calculating angle each point makes with the CoM. Each angle should be Xn+Y, where X is given by the number of points and Y is an offset calculable from the first point. Fail if any are wrong.
4) If no failures have been encountered yet, pass the pointset.


Your algorithm would claim the following list of points was a square:
(-1,0), (-1,0), (1,0), (1,0)
It is not enough to test the angles as you do. You really have to test they are all different.

User avatar
Xanthir
My HERO!!!
Posts: 5425
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Regular N-Gon Algorithm and Big O

Postby Xanthir » Wed Jun 25, 2008 6:07 pm UTC

Ah, true. I had assumed an asymmetric grouping, but symmetric groupings would beat both of my tests.

In that case, there's still an O(n) way to prevent this.

1) Count the number of points (is already done as part of another step). O(n)
2) Create an array of length n, initially filled with 0. O(1)
3) Again, the number of points tells you the angle between each, and the first measured angle tells you the offset. Use this to number each possible angle, and then increment the appropriate array element. O(1) for each operation, O(n) total.
4) At the end, scan through the array. Fail if any element is != 1. O(n)

This'll fail even regularly-distributed groupings, and still leaves us with an O(n) runtime.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Regular N-Gon Algorithm and Big O

Postby Yakk » Wed Jun 25, 2008 6:43 pm UTC

Need the n-gons be convex?

Or would the 5-pointed star be considered an n-gon?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Xanthir
My HERO!!!
Posts: 5425
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Regular N-Gon Algorithm and Big O

Postby Xanthir » Wed Jun 25, 2008 6:48 pm UTC

The original problem statement only gives you a collection of points, with no pathing information. There is no way to distinguish a 5-star from a pentagon.

Pathing information honestly makes this easier, as that functions as a free sorting of the points, allowing you to go with daydalus' original algorithm.

Generally, though, I believe an n-gon is assumed to be a planar graph, giving you only one interpretation of 'regular n-gon'.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

poohat
Posts: 230
Joined: Mon Apr 07, 2008 6:21 am UTC

Re: Regular N-Gon Algorithm and Big O

Postby poohat » Thu Jun 26, 2008 3:43 am UTC

After youve found the midpoint couldnt you use this to perform a translation so that the midpoint is the origin, then do a rotation/shrinkage so that one point lies at (0,1) then express every point in complex polar form and check whether theyre all nth roots unity where n is the number of points of you have.

I think that would be O(n) ?



edit: no it wouldnt because its not checking uniqueness :/

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Regular N-Gon Algorithm and Big O

Postby Yakk » Thu Jun 26, 2008 3:59 am UTC

Xanthir wrote:The original problem statement only gives you a collection of points, with no pathing information. There is no way to distinguish a 5-star from a pentagon.

Pathing information honestly makes this easier, as that functions as a free sorting of the points, allowing you to go with daydalus' original algorithm.

Generally, though, I believe an n-gon is assumed to be a planar graph, giving you only one interpretation of 'regular n-gon'.


*nod*

Hmm. could you consider something with a "saw-tooth" pattern, going up and down in the z-axis, as being a regular n-gon. (same angle between any 3 adjacent sides, same distance)

And if [imath](e^a)^k[/imath] = 1 for k!=0 then, I think, the least z>0 such that [imath](e^a)^b = (e^z)[/imath] will also generate the points in question... right? God damn it, my group theory is rusty.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Xanthir
My HERO!!!
Posts: 5425
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Regular N-Gon Algorithm and Big O

Postby Xanthir » Thu Jun 26, 2008 6:14 pm UTC

Yakk wrote:
Xanthir wrote:The original problem statement only gives you a collection of points, with no pathing information. There is no way to distinguish a 5-star from a pentagon.

Pathing information honestly makes this easier, as that functions as a free sorting of the points, allowing you to go with daydalus' original algorithm.

Generally, though, I believe an n-gon is assumed to be a planar graph, giving you only one interpretation of 'regular n-gon'.


*nod*

Hmm. could you consider something with a "saw-tooth" pattern, going up and down in the z-axis, as being a regular n-gon. (same angle between any 3 adjacent sides, same distance)

And if [imath](e^a)^k[/imath] = 1 for k!=0 then, I think, the least z>0 such that [imath](e^a)^b = (e^z)[/imath] will also generate the points in question... right? God damn it, my group theory is rusty.

I wouldn't consider it an anything-gon, as it's no longer planar. ^_^

If we generalize and ignore that requirement, though, then I think the answer would have to be yes.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 7 guests