Re: Question about an algorithm
- From: Gary <LanceGary@xxxxxxxxx>
- Date: Tue, 10 Jul 2007 20:54:49 -0000
On Jul 10, 9:52 pm, "John H Meyers" <jhmey...@xxxxxxxxxxxxxx> wrote:
On Mon, 09 Jul 2007 09:18:34 -0500, Gary wrote:
Problem: Given a set of points distributed (not necessarily evenly)
around the circumference of a circle, find the smallest number of
points in any semicircle.
My solution: Divide the circumference into an even number of equal
segments. Count the number of points in each segment. Some segments
may contain zero points. Store the segment frequencies in a list (the
order in the list representing position on circumference). Divide the
list in half and count the points in each half, storing the value that
is lowest. Now cycle the list, so that the entry in position 1 becomes
the entry in position n (the last position in the list). Repeat the
division of the list into two, and calculate the number of points in
each half, storing the lowest value. Continue cycling through the list
until you return to the original list. Now examine your list of
smallest counts, and find the minimum. That minimum is the smallest
number of points in any semicircle.
Possible problem: The accuracy of the algorithm will depend on
how finely the original circumference is divided.
Given that now we know this is just for a statistical measure
of non-uniformity, and also apparently that a very large number
of data points is involved, it's clear that we have no interest
in finding the theoretically exact answer, which makes quite
a difference in the approach to take; indeed, after knowing
what this is for, and that there is voluminous data,
I would take exactly this same approach -- divide the circle
into 90 or 100 parts, or as best suits the "coordinates"
in which these points are described, count how many points
lie in each part, and see which consecutive run of 45 or 50
segments (or half the region) has the lowest sum (the other half
necessarily has simultaneously the largest sum, since the grand
total is the constant entire population of points). There is
no value in estimating the answer to any better precision
than its uncertainty, anyway.
A slight computational time saving (offset by longer time
programming and debugging) can come from noting that as
we go from each summation run to the next, we simply
add in one new segment and drop one old segment each time,
so we don't necessarily have to repeat summing an entirely new
whole set of data each time.
People who design electromagnetic antennas, as well as those
who investigate many other physical phenomena, may also
be thinking that any circular distribution might be
describable as a superposition of a "monopole" component,
a "dipole," a "quadrupole," etc., and that this particular
measure is basically responding to only the first component
of this series -- but we always oversimplify things, don't we,
except in alternation with making them overly complex :)
-[ ]-
Thanks for the hint. Your help much appreciated.
Lance
.
- References:
- Question about an algorithm
- From: Gary
- Re: Question about an algorithm
- From: John H Meyers
- Question about an algorithm
- Prev by Date: Re: spherical coordinates in HP 49G
- Next by Date: Re: Question about an algorithm
- Previous by thread: Re: Question about an algorithm
- Next by thread: Re: Question about an algorithm
- Index(es):
Relevant Pages
|
