Abstract | ||
---|---|---|
Let P and Q be simple polygons with vertex sets fp1 ; : : : ; png andfq1 ; : : :, qng, respectively. We present an algorithm to construct a piecewiselinear homeomorphism between P and Q mapping each vertex p i 2 Pto q i 2 Q by constructing isomorphic triangulations of P and Q. Theseisomorphic triangulations consist of O(M log n+n log2n) triangles whereM is the size of the optimal (minimum size) solution. The algorithm runsin O(M log n + n log2n) time. We also give an O(n + L +... |
Year | DOI | Venue |
---|---|---|
1997 | 10.1006/jagm.1995.0808 | J. Algorithms |
Keywords | Field | DocType |
piecewise linear homeomorphisms,simple polygon,computer science,piecewise linear | Discrete mathematics,Polygon,Combinatorics,Disjoint sets,Vertex (geometry),Computational geometry,Isomorphism,Simple polygon,Piecewise linear function,Mathematics,Homeomorphism | Journal |
Volume | Issue | ISSN |
22 | 1 | 0196-6774 |
Citations | PageRank | References |
14 | 1.12 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Himanshu Gupta | 1 | 2653 | 277.86 |
Rephael Wenger | 2 | 441 | 43.54 |