Given
check(p1, p2, polys, points)
for i = 3 to points.size()
rp = generate(i, p1, p2)
if rp in points
polys += rp
A sorted list of the vertices in an n-point polygon can be generated from an edge of the polygon in O(n logn) time.
check(p1, p2, polys, points)
for i = 3 to points.size()
O(n log n)
if rp in points
polys += rp
Determining whether a set of m points is a subset of a set of n
points can be done in O(max(m, n)) time if both sets are sorted
(and m <= n).
check(p1, p2, polys, points)
for i = 3 to points.size()
O(n log n)
if O(n)
O(log n)
A polygon can be inserted into a (sorted) set of n polygons in O(log n) time.
check(p1, p2, polys, points)
for i = 3 to points.size()
O(n log n)
if O(n)
polys += rp
Given a set of n points, the body of the check() iterates
O(n) times,
check(p1, p2, polys, points)
for O(n)
O(n log n)
if O(n)
polys += rp
and the total estimate for check() is O(n2 log n).
Given
find_polys(s)
s' = s
polys = { }
while s not empty
p1 = pick s
foreach p2 in s
check(p1, p2, polys, s')
check(p2, p1, polys, s')
return polys
copying a set of n points takes O(n) time, initialization is constant, as is picking an element of the set.
find_polys(s)
O(n)
O(1)
while O(n)
O(1)
foreach O(n)
O(n^2 log n)
O(n^2 log n)
return polys
The double-nested loop reduces to O(n4 log n), but what does it cost to return the polygons? We could fudge the question by passing the polygon set by reference, which takes constant time, but let's see if we can answer the question as stated.
The real question is "does return polys take more or less time than
O(n4 log n)?" Because it took at most that much time to
create polys, polys can't contain more than a constant factor of
O(n4 log n) polygons, and it should cost no more than that
make and return a copy of polys (assuming polys is unsorted).
This page last modified on 28 April 2004.