Name
Abstract | ||
|---|---|---|
We consider the problem of obtaining "nice" quadrangulations of planar sets of points. For many applications "nice" means that the quadrilaterals obtained are convex if possible and as "fat" or squarish as possible. For a given set of points a quadrangulation, if it exists, may not admit all its quadrilaterals to be convex. In such cases we desire that the quadrangulations have as many convex quadrangles as possible. Solving this problem optimally is not practical. Therefore we propose and experimentally investigate a heuristic approach to solve this problem by converting "nice" triangulations to the desired quadrangulations with the aid of maximum matchings computed on the dual graph of the triangulations. We report experiments on several versions of this approach and provide theoretical justification for the good results obtained with one of these methods. The results of our experiments are particularly relevant for those applications in scattered data interpolation which require quadrangulations that should stay faithful to the original data. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0167-8396(02)00133-4 | Computer Aided Geometric Design |
Keywords | Field | DocType |
dual graph,planar set,triangulations,maximum matchings,mesh generation,theoretical justification,convex quadrangle,heuristic approach,quadrangulations,original data,fixed point,scattered data interpolation,matchings,problem optimally,good result,maximum matching | Discrete mathematics,Combinatorics,Heuristic,Interpolation,Regular polygon,Triangulation (social science),Dual graph,Quadrilateral,Fixed point,Mathematics,Mesh generation | Journal |
Volume | Issue | ISSN |
19 | 7 | Computer Aided Geometric Design |
Citations | PageRank | References |
4 | 0.46 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prosenjit K. Bose | 1 | 2336 | 293.75 |
| Suneeta Ramaswami | 2 | 228 | 23.87 |
| Godfried Toussaint | 3 | 85 | 13.01 |
| Alain Turki | 4 | 4 | 0.46 |