Triangulace s hranovými kritérii - Šípkové Růženky právem nebo neprávem zapomenuté?

Kolingerová, Ivana

Pokroky matematiky, fyziky a astronomie, Tome 65 (2020) no. 4, pp. 223-233

Résumé (VO)

Planární triangulace zadané množiny bodů je častým základem aplikací, proto vzniklo mnoho metod, jak triangulaci zkonstruovat. Všechny metody se snaží dospět k trojúhelníkům "co nejrovnostrannějším", což je možné zařídit optimalizací úhlových nebo hranových kritérií. Vzhledem k vynikajícím vlastnostem, všestrannosti a snadné konstrukci Delaunayovy triangulace, nejdůležitější a nejznámější představitelky úhlových kritérií, stojí ostatní typy triangulace, zejména hranově optimalizované, poněkud ve stínu. V tomto článku chceme připomenout dvě nejvýznamnější méně úspěšné hranově optimalizované konkurentky Delaunayovy triangulace, a to greedy triangulaci a lokálně optimální triangulaci, a předložit argumenty ve prospěch i v neprospěch jejich častějšího využití.

Détail

Classification : 68U05

Bibliographie

[1] Agarwal, P. K., Kaplan, H., Rubin, N.: Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions. Discrete Comput. Geom. 54 (2015), 871–904. | DOI | MR

[2] Aichholzer, O., Aurenhammer, F., Cheng, S. W., Katoh, N., Rote, G., Taschwer, M., Xu, Y. F.: Triangulations intersect nicely. Discrete Comput. Geom. 16 (1996), 339–359. | DOI | MR

[3] Aichholzer, O., Aurenhammer, F., Hainz, R.: New results on MWT subgraphs. TR Nr. 140. Institute for Theoretical Computer Science, Graz University of Technology, 1998. | MR

[4] Aurenhammer, F.: Voronoi diagrams – a survey of a fundamental geometric data structure. ACM Comput. Surv. 23 (1991), 345–405. | DOI

[5] Bartánus, M., Ferko, A., Mag, R., Niepel, L., Plachetka, T., Šikudová, E.: New heuristics for minimum weight triangulation. In: WSCG 1996 Conference Proceedings, University of West Bohemia, Pilsen, 1996, 31–40.

[6] Beirouti, R., Snoeyink, J.: Implementations of the LMT heuristic for minimum weight triangulation. In: Proc. 14th Annual Symposium on Comput. Geom., Minneapolis, 1998, 96–105.

[7] Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., Tan, T. S.: Edge insertion for optimal triangulations. Discrete Comput. Geom. 10 (1993), 47–65. | DOI | MR

[8] Bern, M., Eppstein, D.: Mesh generation and optimal triangulation. In: Computing in Euclidean Geometry, 2nd Edition, Lecture Notes Series on Computing, Vol. 4, World Scientific, Singapore, 1995, 47–123. | MR

[9] de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational geometry. Algorithms and applications. Springer, Heidelberg, 1997. | DOI | MR

[10] Bose, P., Devroye, L., Evans, W.: Diamonds are not a minimum weight triangulation's best friend. Internat. J. Comput. Geom. 12 (2002), 445–454. | DOI | MR

[11] Cignoni, P., Montani, C., Perego, R., Scopigno, R: Parallel 3D Delaunay triangulation. In: Proc. of Eurographics ’93, 1993, C129–C142.

[12] Das, G., Joseph, D.: Which triangulations approximate the complete graph. In: Proceedings of the International Symposium on Optimal Algorithms, Lecture Notes in Computer Science, Vol. 401, Springer-Verlag, 1989, 168–183.

[13] Dickerson, M. T., Drysdale, R. L., McElfresh, S., Welzl, E.: Fast greedy triangulation algorithms. In: Proc. 10th Annual Symposium on Comput. Geom., 1994, 211–220. | MR

[14] Dickerson, M. T., Keil, J. M., Montague, M. H.: A large subgraph of the minimum weight triangulation. Discrete Comput. Geom. 18 (1997), 289–304. | DOI | MR

[15] Dickerson, M. T., Montague, M. H.: A (usually?) connected subgraph of the minimum weight triangulation. In: Proc. 12th Symposium on Comput. Geom., Philadelphia, 1996, 204–213.

[16] Drysdale, R. L. S., Rote, G., Aichholzer, O.: A simple linear time greedy triangulation algorithm for uniformly distributed points. IIG-Report-Series-408. Technische Universität Graz, 1995.

[17] Dyn, N., Levin, D., Rippa, S.: Data dependent triangulations for piecewise linear interpolation. IMA J. Numer. Anal. 10 (1990), 137–154. | DOI | MR

[18] Edelsbrunner, H., Tan, T. S.: A quadratic time algorithm for the minmax length triangulation. SIAM J. Comput. 22 (1991), 527–551. | DOI | MR

[19] Edelsbrunner, H., Tan, T. S., Waupotisch, R.: An $O(N^{2} \log N)$ time algorithm for the minmax angle triangulation. SIAM J. Stat. Sci. Comput. 13 (1992), 994–1008. | DOI | MR

[20] Eppstein, D.: The farthest point Delaunay triangulation minimizes angles. Comp. Geom.-Theor. Appl. 1 (1992), 143–148. | DOI | MR

[21] Fang, Y.: An improved Lawson local-optimization procedure and its applications. TR, University of Victoria, 2018.

[22] Gilbert, P. D.: New results on planar triangulations. Tech. Rep. ACT-15. Coord. Sci. Lab., University of Illinois, Urbana, 1979.

[23] Goldman, S.: A space efficient greedy triangulation algorithm. Inform. Process. Lett. 32 (1989), 191–196. | DOI | MR

[24] Haas, A.: Solving large-scale minimum-weight triangulation instances to provable optimality. In: 34th International Symposium on Computational Geometry, 2018, article no. 44, 14 pages. | MR

[25] Hardwick, J. C.: Implementation and evaluation of an efficient parallel Delaunay triangulation algorithm. In: Proceedings of the 10th Annual Symposium on Parallel Algorithms and Architectures, 1997, 22–25.

[26] Chen, M. B., Chuang, T. R., Wu, J. J.: Efficient parallel implementations of 2D Delaunay triangulation with high performance Fortran. In: Proceedings of the 10th SIAM Conference on Parallel Processing for Scientific Computing, SIAM Press, 2001.

[27] Chin, F. Y., Wang, C. A.: On greedy tetrahedralization of points in 3D. In: Algorithms and Computation, Lecture Notes in Computer Science, Vol. 834, 1994, 532–540. | MR

[28] Cho, H. G.: On the expected number of common edges in Delaunay and greedy triangulation. Journal WSCG 5 (1997), 50–59.

[29] Chrisochoides, N., Sukup, F.: Task parallel implementation of the Bawyer-Watson algorithm. In: Proceedings of the 5th International Conference on Numerical Generation in Computational Fluid Dynamic and Related Fields, Mississippi State University, 1996.

[30] Kim, Y. S., Park, D. G., Jung, H. Y., Cho, H. G., Dong, J. J., Ku, K. J.: An improved TIN compression using Delaunay triangulation. In: Proceedings of Seventh Pacific Conference on Computer Graphics and Applications, Seoul, 1999, 118–125.

[31] Kirkpatrick, D. G.: A note on Delaunay and optimal triangulations. Inform. Process. Lett. 10 (1980), 127–128. | DOI | MR

[32] Kohout, J., Kolingerová, I., Žára, J.: Practically oriented parallel Delaunay triangulation in $E^{2}$ for computers with shared memory. Comput. Graph. 28 (2004), 703–718. | DOI | MR

[33] Kohout, J., Kolingerová, I., Žára, J.: Parallel Delaunay triangulation in $E^{2}$ and $E^{3}$ for computers with shared memory. Parallel Comput. 31 (2005), 491–522. | DOI | MR

[34] Kolingerová, I.: Greedy triangulation improvement over lookahead search. In: Computer Engineering and Informatics ’99 Proceedings, STU, Košice, 1999, 34–39.

[35] Kolingerová, I., Dolák, M., Strych, V.: Eliminating contour line artefacts by using constrained edges. Comput. Geosci. 35 (2009), 1975–1987. | DOI

[36] Kolingerová, I., Ferko, A.: Multicriteria-optimized triangulations. Visual Comput. 17 (2001), 380–395. | DOI

[37] Kolingerová, I., Vomáčka, T., Maňák, M., Ferko, A.: Neighbourhood graphs and locally minimal triangulations. In: Transactions on Computational Science XXXIII, Springer, Heidelberg, 2018, 115–127. | MR

[38] Krznaric, D.: Progress in hierarchical clustering & minimum weight triangulation. PhD Thesis. University of Lund, Sweden, 1997.

[39] Lawson, C. L.: Transforming triangulations. Discrete Math. 3 (1972), 365–372. | DOI | MR

[40] Lawson, C. L.: Software for C1 surface interpolation. In: Rice, J. R. C.: Mathematical Software III, Academic Press, New York, 1977, 161–194. | MR

[41] Lee, F.: Constructing the constrained Delaunay triangulation on the Intel Paragon. In: Proceedings of the 13th Annual Symposium on Computational Geometry, ACM, 1997, 464–467.

[42] Levcopoulos, Ch.: An $\Omega (\sqrt{n})$ lower bound for the nonoptimality of the greedy triangulation. Inform. Process. Lett. 2 (1987), 247–251. | DOI | MR

[43] Levcopoulos, Ch., Krznaric, D.: The greedy triangulation can be computed from the Delaunay triangulation in linear time. Comput. Geom. 14 (1999), 197–220. | DOI | MR

[44] Levcopoulos, Ch., Lingas, A.: Fast algorithms for greedy triangulation. Proc. of the 2nd Scandinavian Workshop on Algorithm. Theory, Lecture Notes in Computer Science, Vol. 447, Springer-Verlag, Berlin, 1990, 238–250. | MR

[45] Lingas, A.: The greedy and Delaunay triangulations are not bad in the average case. Inform. Process. Lett. 22 (1986), 25–31. | DOI | MR

[46] Lingas, A.: Greedy triangulation can be efficiently implemented in the average case. In: Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 344, 1988, 253–261. | MR

[47] Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point-set is NP-complete. In: 24th Canadian Conference on Computational Geometry, 2012, 127–132. | MR

[48] Magová, I., Ferko, A., Niepel, L.: On edges elimination for the shortest mesh. Journal WSCG 5 (1997), 396–403.

[49] Manacher, G. K., Zobrist, A. L.: Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation. Inform. Process. Lett. 9 (1979), 31–34. | DOI | MR

[50] Manacher, G. K., Zobrist, A. L.: Probabilistic methods with heaps for fast-average-case greedy algorithms. Adv. Comput. Res. 1 (1983), 261–278.

[51] Mulzer, W., Rotte, G.: Minimum-weight triangulation is NP-hard. J. ACM 55 (2008), article no. 11, 29 pages. | DOI | MR

[52] Okabe, A., Boots, B., Sugihara, K.: Spatial tesselations: concepts and applications of Voronoi diagrams. John Wiley, Chichester, 1992. | MR

[53] O'Rourke, J.: Computational geometry in C. Cambridge University Press, New York, 1994. | MR

[54] Osherovich, E., Bruckstein, M. M.: All triangulations are reachable via sequences of edge flips: an elementary proof. Comput. Aided Geom. Design 25 (2008), 157–161. | DOI | MR

[55] Partyk, M., Polec, J., Kolingerová, I., Březina, A.: Triangulations in a hybrid scheme for shape independent transform coding. In: Advanced Concepts for Intelligent Vision Systems, Ghent, 2003, 137–141.

[56] Pilz, A.: Flip distance between triangulations of a planar point set is APX-hard. Comput. Geom. 47 (2014), 589–604. | DOI | MR

[57] Preparata, F. P., Shamos, M. I.: Computational geometry: an introduction. Springer, Heidelberg, 1985. | DOI | MR

[58] Puppo, E., Davis, L. S., DeMenthon, D., Teng, A.: Parallel terrain triangulation. Int. J. Geogr. Inf. Syst. 8 (1994), 105–128. | DOI

[59] Vomáčka, T., Kolingerová, I., Maňák, M.: Kinetic locally minimal triangulation: theoretical evaluation and combinatorial analysis. Visual Comput. 36 (2020), 757–765. | DOI

[60] Yu, X., Morse, B. S., Sederberg, T. W.: Image reconstruction using data-dependent triangulation. IEEE Comput. Graph. 21 (2001), 62–68. | DOI