David Eppstein - Publications

Publications with Ethan Kim

• Approximate Topological Matching of Quadrilateral Meshes.
  D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.
  Proc. IEEE Int. Conf. Shape Modeling and Applications (SMI 2008), Stony Brook, New York, pp. 83–92.
  The Visual Computer 25 (8): 771–783, 2009.

  We formalize problems of finding large approximately-matching regions of two related but not completely isomorphic quadrilateral meshes, show that these problems are NP-complete, and describe a natural greedy heuristic that is guaranteed to find good matches when the mismatching parts of the meshes are small.

  (Preprint)

• Motorcycle graphs: canonical quad mesh partitioning.
  D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.
  Proc. 6th Symp. Geometry Processing, Copenhagen, Denmark, 2008.
  Computer Graphics Forum 27 (5): 1477–1486, 2008.

  We use a construction inspired by the motorcycle graphs previously used in straight skeleton construction, to partition quadrilateral meshes into a small number of structured submeshes. Our construction is canonical in that two copies of the same mesh will always be partitioned in the same way, and can be used to speed up graph isomorphism computations for geometric models in feature animation.

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

Semi-automatically filtered from a common source file.