David Eppstein – Publications

Publications with Doruk Korkmaz

• Defining equitable geographic districts in road networks via stable matching.
  D. Eppstein, M. T. Goodrich, D. Korkmaz, and N. Mamano.
  arXiv:1706.09593
  Proc. 25th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM SIGSPATIAL 2017), Redondo Beach, California, pp. 52:1–52:4.

  We cluster road networks (modeled as planar graphs, or more generally as graphs obeying a separator theorem) with a given set of cluster centers, by matching graph vertices to centers stably according to distance: no unmatched vertex and center should have smaller distances than the matched pairs for the same points. We provide a separator-based data structure for dynamic nearest neighbor queries in planar or separated graphs, which allows the optimal stable clustering to be constructed in time O(n^3/2log n). We also experiment with heuristics for fast practical construction of this clustering.