Finding Equitable Convex Partitions of Points and Its Applications

Yinyu Ye
Department of Management Science and Engineering
Stanford University


Wednesday, February 28, 2006
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:

Given a convex polygon specified by its vertices, and other k points (hub/sever) located on the polygon, we present a fast algorithm to partition the polygon into k pieces such that the following three properties hold: (i) the closure of each piece is a convex polygon, (ii) each piece contains exactly one of the k points, (iii) every piece has the equitable area. We also show its applications in multi-depot vehicle routing, load-balanced network designing, client/server supply chaining, etc.

This is joint work with John Gunnar Carlsson and Benjamin Armbruster. This research is supported by Boeing.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html