Motorcycle Graphs: Canonical Quad Mesh Partitioning

dc.contributor.authorEppstein, Daviden_US
dc.contributor.authorGoodrich, Michael T.en_US
dc.contributor.authorKim, Ethanen_US
dc.contributor.authorTamstorf, Rasmusen_US
dc.date.accessioned2015-02-21T17:32:32Z
dc.date.available2015-02-21T17:32:32Z
dc.date.issued2008en_US
dc.description.abstractWe describe algorithms for canonically partitioning semi-regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad meshes. Our partitions may be used to efficiently find isomorphisms between quad meshes. In addition, they may be used as a highly compressed representation of the original mesh. These partitions can be constructed in sublinear time from a list of the extraordinary vertices in a mesh. We also study the problem of further reducing the number of submeshes in our partitions-we prove that optimizing this number is NP-hard, but it can be efficiently approximated.en_US
dc.description.number5en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume27en_US
dc.identifier.doi10.1111/j.1467-8659.2008.01288.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages1477-1486en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2008.01288.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltden_US
dc.titleMotorcycle Graphs: Canonical Quad Mesh Partitioningen_US
Files