David Eppstein - Publications

Publications with Kevin Wortman

• Minimum dilation stars.
  D. Eppstein and K. Wortman.
  arXiv:cs.CG/0412025.
  21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 321–326.
  Comp. Geom. Theory & Applications 37 (1): 27–37, 2007.

  We show how to test the dilation of a star, embedded in a Euclidean space of bounded dimension, in time O(n log n), and how to find the star center that has the minimum dilation for a given set of leaf points in randomized expected time O(n log n). For two-dimensional points, we can find the minimum dilation center, constrained to be one of the input points, in time O(n 2^α(n) log²n). The unconstrained center placement algorithm involves quasiconvex programming, and is used as a subroutine in the constrained center placement algorithm.

  (SoCG05 talk slides)

• Approximate weighted farthest neighbors and minimum dilation stars.
  J. Augustine, D. Eppstein, and K. Wortman.
  arXiv:cs.CG/0602029.
  Proc. 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam.
  Springer, Lecture Notes in Comp. Sci. 6196, 2010, pp. 90–99.
  Discrete Mathematics, Algorithms and Applications 2 (4): 553–565, 2010.

  The problem is to quickly find, in a set of sites with weights, the site maximizing the product of its weight with its distance from the query point. Our solution combines known results on core-sets with a reduction from the weighted to the unweighted problem that works in any metric space. This leads to fast approximation algorithms for the constrained minimum dilation star problem in any fixed dimension.

• Planar Voronoi diagrams for sums of convex functions, smoothed distance and dilation.
  M. Dickerson, D. Eppstein, and K. Wortman.
  arXiv:0812.0607.
  7th Int. Symp. Voronoi Diagrams in Science and Engineering (ISVD 2010), Quebec City, Canada, pp. 13–22.

  Investigates Voronoi diagrams for a "smoothed distance" in which the distance between two points p and q is inversely weighted by the perimeter of triangle opq for a fixed point o, its relation to dilation of star networks centered at o, and its generalization to minimization diagrams of certain convex functions. When the function to be minimized is suitably well-behaved, its level sets form pseudocircles, the bisectors of the minimization diagram form pseudoline arrangements, and the diagram itself has linear complexity.

• Optimal embedding into star metrics.
  D. Eppstein and K. Wortman.
  arXiv:0905.0283.
  Algorithms and Data Structures Symposium (WADS), Banff, Canada (best paper award).
  Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 290–301.

  We provide an O(n³ log²n) algorithm for finding a non-distance-decreasing mapping from a given metric into a star metric with as small a dilation as possible. The main idea is to reduce the problem to one of parametric shortest paths in an auxiliary graph. Specifically, we transform the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles. We find a new strongly polynomial time algorithm for this problem, and use it to solve the star metric embedding problem.

  (Slides)

• Optimal angular resolution for face-symmetric drawings.
  D. Eppstein and K. Wortman.
  arXiv:0907.5474.
  J. Graph Algorithms and Applications 15 (4): 551–564, 2011.

  We consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media. Among all drawings of this type, we show how to find the one with optimal angular resolution. The solution involves a transformation from the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles.

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.