×

zbMATH — the first resource for mathematics

Meshes preserving minimum feature size. (English) Zbl 1374.68633
Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 258-273 (2012).
Summary: The minimum feature size of a planar straight-line graph is the minimum distance between a vertex and a nonincident edge. When such a graph is partitioned into a mesh, the degradation is the ratio of original to final minimum feature size. For an \(n\)-vertex input, we give a triangulation (meshing) algorithm that limits degradation to only a constant factor, as long as Steiner points are allowed on the sides of triangles. If such Steiner points are not allowed, our algorithm realizes \({O}(\lg n)\) degradation. This addresses a 14-year-old open problem by M. Bern et al. [Int. J. Comput. Geom. Appl. 5, No. 1–2, 171–192 (1995; Zbl 0818.68139)].
For the entire collection see [Zbl 1253.68016].

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aloupis, G., Demaine, E., Demaine, M., Dujmovic, V., Iacono, J.: Meshes preserving minimum feature size. Technical report arXiv:0908:2493 (2011) · Zbl 1374.68633
[2] Bern, M., Dobkin, D., Eppstein, D.: Triangulating polygons without large angles. Interational Journal of Computational Geometry & Applications 5(1-2), 171–192 (1995) · Zbl 0818.68139 · doi:10.1142/S0218195995000106
[3] Bern, M., Eppstein, D.: Mesh generation and optimal triangulation. In: Du, D.-Z., Hwang, F.K.-M. (eds.) Computing in Euclidean Geometry, 2nd edn. Lecture Notes Series on Computing, vol. 4, pp. 47–123. World Scientific (1995) · doi:10.1142/9789812831699_0003
[4] Dey, T.K.: Delaunay mesh generation of three dimensional domains. Technical Report OSU-CISRC-09/07-TR64, Ohio State University (October 2007)
[5] Erickson, J.: Nice point sets can have nasty delaunay triangulations. Discrete & Computational Geometry 30(1) (July 2003) · Zbl 1038.68129 · doi:10.1007/s00454-003-2927-4
[6] Frederickson, G.N.: Dissections: Plane and Fancy. Cambridge University Press (November 1997) · Zbl 0939.52008
[7] Hudson, B., Miller, G., Phillips, T.: Sparse Voronoi Refinement. In: Proceedings of the 15th International Meshing Roundtable, Birmingham, Alabama, pp. 339–356. Springer (September 2006) · doi:10.1007/978-3-540-34958-7_20
[8] Lowry: Solution to question 269, [proposed] by Wallace, W. In: Leybourn, T. (ed.) Mathematical Repository, vol. 3, part 1, pp. 44–46. W. Glendinning, London (1814)
[9] Ruppert, J.: A new and simple algorithm for quality 2-dimensional mesh generation. In: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, Texas, pp. 83–92 (1993) · Zbl 0801.68163
[10] Shewchuk, J.R.: Theoretically guaranteed Delaunay mesh generation–in practice. Short course at 13th International Meshing Roundtable (2004), http://www.cs.berkeley.edu/ jrs/papers/imrtalk.pdf
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.