David Eppstein - Publications

• Beta-skeletons have unbounded dilation.
  D. Eppstein.
  Tech. Rep. 96-15, ICS, UCI, 1996.
  arXiv:cs.CG/9907031.
  Comp. Geom. Theory & Applications 23: 43–52, 2002.

  Beta-skeletons are geometric graphs used among other purposes for empirical network analysis and minimum weight triangulation. A fractal construction shows that, for any beta>0, the beta-skeleton of a point set can have arbitrarily large dilation: Omega(n^c), where c is a constant depending on beta and going to zero in the limit as beta goes to zero. In particular this applies to the Gabriel graph. We also show upper bounds on dilation of the same form.

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

Semi-automatically filtered from a common source file.