Voronoi cells in Python? --- Exact spatial model
Hi guys,
I like Kristofer's idea of using geometry and volumes to model elections
with essentially an infinite number of voters. Unfortunately I've never
really worked with computational geometry in any form, so I'm not really
familiar with the tools and techniques. I found a software library that
might have the tools required to implement Kristofer's idea, but I can't
quite figure out how to make it work.
The scipy.spatial module is a Python front-end for the QHull library. If
you give it a set of points in N dimensions it will compute the Voronoi
cells and give you its vertices. You can convert the vertices into a convex
hull, and it can compute the volume of a convex hull.
http://www.qhull.org/
https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.Voronoi.html
https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.ConvexHull.html
The next problem that I ran into is that most of the Voronoi cells have an
infinite volume because they are unbounded. I could not find any way to
define a bounding box to "clip" the Voronoi cells. One poster on
StackOverflow suggested a solution:
- Start with your list of candidates / points and your bounding box.
- Reflect the points along each side of the bounding box.
- Compute the Voronoi cells of that.
Reflecting points along each side of the box forces the Voronoi cells that
you care about to actually stop at the walls of the box exactly. You can
later filter out all the cells outside the bounding box to get the ones you
really need.
Ok. So now you can figure out what fraction of voters will select candidate
'A' first. But that was only step one. What we really want to do is compute
Voronoi cells and volumes many times with different lists of candidates to
gradually work out the entire ballots. For example, save the Voronoi cell
for 'A'-voters, remove 'A' and re-run the Voronoi cell calculator. So now
the 'A'-voters will be in different cells. Compute the intersection of
every cell with the old 'A'-voters cell and you now have the 'A>B'-cell,
the 'A>C'-cell and so on.
The only problem? The library doesn't have an obvious way to take the
intersection of two convex hulls. What it does have is a way to define a
shape as the intersection of multiple half-spaces.
https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html
But I can't figure out how to use this to intersect two convex hulls. You'd
think that it would be doable, and that someone should have solved this
problem already but I could not find a solution. Someone asked this on
StackOverflow and they were pointed to yet another library:
https://stackoverflow.com/questions/70452216/how-to-find-the-intersection-of-2-convex-hulls
At this point everything is looking harder than it needs to be, and I
couldn't go any further. Does anyone either know how to use scipy.spatial
or know of an entirely different toolkit that can take intersections of
Voronoi cells?
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
Some additional thoughts:
- The scipy.spatial.HalfspaceIntersection defines a convex hull as an
intersection of half-spaces. If we can express the Voronoi cells this way,
then intersections are potentially very easy. The intersection of two
volumes defined by a list of half-space inequalities is just stacking all
the inequalities.
HOWEVER...
-
I'm not yet sure how to convert a scipy.spatial.Voronoi cell into a
bunch of inequalities. -
The function also asks for an interior point. I don't really know how to
get one, but the documentation says "it can be obtained by linear
programming." --- so maybe this is a problem that someone that works with
MIPS knows how to solve. For the first Voroni space, the candidate is
obviously an interior point. But once you start taking intersections, I
don't really know what to do.
https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html
Cheers,
Daniel
On Sat, Jan 29, 2022 at 1:35 PM Daniel Carrera dcarrera@gmail.com wrote:
Hi guys,
I like Kristofer's idea of using geometry and volumes to model elections
with essentially an infinite number of voters. Unfortunately I've never
really worked with computational geometry in any form, so I'm not really
familiar with the tools and techniques. I found a software library that
might have the tools required to implement Kristofer's idea, but I can't
quite figure out how to make it work.
The scipy.spatial module is a Python front-end for the QHull library. If
you give it a set of points in N dimensions it will compute the Voronoi
cells and give you its vertices. You can convert the vertices into a convex
hull, and it can compute the volume of a convex hull.
https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.Voronoi.html
https://docs.scipy.org/doc//scipy/reference/generated/scipy.spatial.ConvexHull.html
The next problem that I ran into is that most of the Voronoi cells have an
infinite volume because they are unbounded. I could not find any way to
define a bounding box to "clip" the Voronoi cells. One poster on
StackOverflow suggested a solution:
- Start with your list of candidates / points and your bounding box.
- Reflect the points along each side of the bounding box.
- Compute the Voronoi cells of that.
Reflecting points along each side of the box forces the Voronoi cells that
you care about to actually stop at the walls of the box exactly. You can
later filter out all the cells outside the bounding box to get the ones you
really need.
Ok. So now you can figure out what fraction of voters will select
candidate 'A' first. But that was only step one. What we really want to do
is compute Voronoi cells and volumes many times with different lists of
candidates to gradually work out the entire ballots. For example, save the
Voronoi cell for 'A'-voters, remove 'A' and re-run the Voronoi cell
calculator. So now the 'A'-voters will be in different cells. Compute the
intersection of every cell with the old 'A'-voters cell and you now have
the 'A>B'-cell, the 'A>C'-cell and so on.
The only problem? The library doesn't have an obvious way to take the
intersection of two convex hulls. What it does have is a way to define a
shape as the intersection of multiple half-spaces.
https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html
But I can't figure out how to use this to intersect two convex hulls.
You'd think that it would be doable, and that someone should have solved
this problem already but I could not find a solution. Someone asked this on
StackOverflow and they were pointed to yet another library:
https://stackoverflow.com/questions/70452216/how-to-find-the-intersection-of-2-convex-hulls
At this point everything is looking harder than it needs to be, and I
couldn't go any further. Does anyone either know how to use scipy.spatial
or know of an entirely different toolkit that can take intersections of
Voronoi cells?
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
--
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
On 29.01.2022 20:35, Daniel Carrera wrote:
Hi guys,
I like Kristofer's idea of using geometry and volumes to model elections
with essentially an infinite number of voters. Unfortunately I've never
really worked with computational geometry in any form, so I'm not really
familiar with the tools and techniques. I found a software library that
might have the tools required to implement Kristofer's idea, but I can't
quite figure out how to make it work.
The scipy.spatial module is a Python front-end for the QHull library. If
you give it a set of points in N dimensions it will compute the Voronoi
cells and give you its vertices. You can convert the vertices into a
convex hull, and it can compute the volume of a convex hull.
I haven't investigated QHull in detail, but as far as I know convex
polytopes are usually represented (mathematically) in one of two ways:
as a number of vertices (the vertex representation) or as a number of
linear inequalities that all have to be satisfied (the half-space
representation).
The bad news is that going from one representation to another can be
pretty costly. See https://mathoverflow.net/a/112441. Then again, so is
determining the volume of a c.p., yet QHull can do that in practice.
I'm surprised that QHull doesn't support facet enumeration, though.
The obvious way to do limit Voronoi cells would be to intersect them
with the box that covers the bounds of issue space... but you'd need
intersection functionality to do that, too.
-km
How about this approach:
Working by unions instead of intersections.
For working out the bugs, start with N=20 points randomly sampled from the
standard unit cube [0, 1]^3, with sufficiently many digits of precision to
avoid ties in what follows.
1.First assume, every point represents both a voter and a candidate.
Find each voter's ranking of all N candidates. With enough precision and
randomness in the random number generator, the rankings will be strict and
complete.
N(N-1)/2 pairwise distance calculations, followed by N sorts to find each
voter/candidate's preference order.
- Now suppose we want to consider a subset K of the original set kappa of
N candidates.
This can be accomplished by withdrawing the candidates of
(kappa-K) one by one, adjusting the voter rankings of the remaining
candidates, as in any elimination method.
This results in a set of factions distributed among the remaining winners.
-
Find the winners of various methods, etc
-
To get another ballot set, assign different weights to the initial N
points, and go back to step 2.
If K is kept the same, the factions will not change, except for their
weights.
Change K from time to time, and eventually go all of the way back to step 1.
El sáb., 29 de ene. de 2022 3:21 p. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
On 29.01.2022 20:35, Daniel Carrera wrote:
Hi guys,
I like Kristofer's idea of using geometry and volumes to model elections
with essentially an infinite number of voters. Unfortunately I've never
really worked with computational geometry in any form, so I'm not really
familiar with the tools and techniques. I found a software library that
might have the tools required to implement Kristofer's idea, but I can't
quite figure out how to make it work.
The scipy.spatial module is a Python front-end for the QHull library. If
you give it a set of points in N dimensions it will compute the Voronoi
cells and give you its vertices. You can convert the vertices into a
convex hull, and it can compute the volume of a convex hull.
I haven't investigated QHull in detail, but as far as I know convex
polytopes are usually represented (mathematically) in one of two ways:
as a number of vertices (the vertex representation) or as a number of
linear inequalities that all have to be satisfied (the half-space
representation).
The bad news is that going from one representation to another can be
pretty costly. See https://mathoverflow.net/a/112441. Then again, so is
determining the volume of a c.p., yet QHull can do that in practice.
I'm surprised that QHull doesn't support facet enumeration, though.
The obvious way to do limit Voronoi cells would be to intersect them
with the box that covers the bounds of issue space... but you'd need
intersection functionality to do that, too.
-km
Election-Methods mailing list - see https://electorama.com/em for list
info