# [EM] RE : Comments on the Yee/Bolson/et.al. pictures

Warren Smith wds at math.temple.edu
Fri Dec 22 08:25:48 PST 2006

``` [EM] RE : Comments on the Yee/Bolson/et.al. pictures
Voronoi diagram of N points in plane is computable in O(NlogN) time
by methods that are nowadays standard.  (See Preparata & Shamos book,
Mulmuley book, etc; also equivalent thing [but planar dual]
is "Delaunay triangulation".)

Not a trivial program to write, though.  Better to steal it.

By "c" I meant "a constant."

Approval with mean-as-threshold seemed to "look bad" in the sense that
it could prevent some candidates from ever winning, and make their winning regions
lie far away from them if they existed.   (This is assuming I believe the pictures
I saw, which due to incorrect tiebreaking, I don't necessarily.  There were also some
other interesting high-nonconvexity phenomena in tose pictures which again I do not
necessarily believe due to incorrect tiebreaking.)

>Why implement normalized range voting? That would just be somewhat off
>from the SU graph. I'm not even sure you would see the difference.

It could be quite different.  And I'd like to see how it differs and how much
it differs from the SU graph.  Also, normalized range voting with integer scores (0-9, say)
as opposed to continuum scores, might show some "sawtooth" effects due to
roundoff to integers, which might also be interesting.

Finally, for those who want to speed up their code, I suggest this simple hack:
keep enlarging the #voters by a factor of 1.1 each election, until you get
10 elections in a row all with the same winner, or until you get a large enough number of voters
that you feel like quitting.  The point is, most pixels are elections that are "easy to call"
and you want to terminate fast on those pixels with a fast decision.  The hard-to-call-election
pixels, you perform full work on.  (The value of "1.1" is adjusted to get highest speed.)

wds

```