| Title:
|
Triangulace s hranovými kritérii - Šípkové Růženky právem nebo neprávem zapomenuté? (Czech) |
| Title:
|
Triangulations With Edge Criteria - Sleeping Beauties Rightly or Wrongly Forgotten? (English) |
| Author:
|
Kolingerová, Ivana |
| Language:
|
Czech |
| Journal:
|
Pokroky matematiky, fyziky a astronomie |
| ISSN:
|
0032-2423 |
| Volume:
|
65 |
| Issue:
|
4 |
| Year:
|
2020 |
| Pages:
|
223-233 |
| Summary lang:
|
Czech |
| . |
| Category:
|
math |
| . |
| Summary:
|
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í. (Czech) |
| MSC:
|
68U05 |
| . |
| Date available:
|
2020-12-02T16:51:15Z |
| Last updated:
|
2023-09-13 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148477 |
| . |
| Reference:
|
[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. MR 3416904, 10.1007/s00454-015-9729-3 |
| Reference:
|
[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. MR 1414960, 10.1007/BF02712872 |
| Reference:
|
[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 1688112 |
| Reference:
|
[4] Aurenhammer, F.: Voronoi diagrams – a survey of a fundamental geometric data structure.. ACM Comput. Surv. 23 (1991), 345–405. 10.1145/116873.116880 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[7] Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., Tan, T. S.: Edge insertion for optimal triangulations.. Discrete Comput. Geom. 10 (1993), 47–65. MR 1215322, 10.1007/BF02573962 |
| Reference:
|
[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 1239190 |
| Reference:
|
[9] de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational geometry. Algorithms and applications.. Springer, Heidelberg, 1997. MR 1470713, 10.1007/978-3-662-03427-9_1 |
| Reference:
|
[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. MR 1945593, 10.1142/S0218195902000979 |
| Reference:
|
[11] Cignoni, P., Montani, C., Perego, R., Scopigno, R: Parallel 3D Delaunay triangulation.. In: Proc. of Eurographics ’93, 1993, C129–C142. |
| Reference:
|
[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. |
| Reference:
|
[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 1452410 |
| Reference:
|
[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. MR 1487646, 10.1007/PL00009320 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[17] Dyn, N., Levin, D., Rippa, S.: Data dependent triangulations for piecewise linear interpolation.. IMA J. Numer. Anal. 10 (1990), 137–154. MR 1036653, 10.1093/imanum/10.1.137 |
| Reference:
|
[18] Edelsbrunner, H., Tan, T. S.: A quadratic time algorithm for the minmax length triangulation.. SIAM J. Comput. 22 (1991), 527–551. MR 1219039, 10.1137/0222036 |
| Reference:
|
[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. MR 1166172, 10.1137/0913058 |
| Reference:
|
[20] Eppstein, D.: The farthest point Delaunay triangulation minimizes angles.. Comp. Geom.-Theor. Appl. 1 (1992), 143–148. MR 1154641, 10.1016/0925-7721(92)90013-I |
| Reference:
|
[21] Fang, Y.: An improved Lawson local-optimization procedure and its applications.. TR, University of Victoria, 2018. |
| Reference:
|
[22] Gilbert, P. D.: New results on planar triangulations.. Tech. Rep. ACT-15. Coord. Sci. Lab., University of Illinois, Urbana, 1979. |
| Reference:
|
[23] Goldman, S.: A space efficient greedy triangulation algorithm.. Inform. Process. Lett. 32 (1989), 191–196. MR 1000272, 10.1016/0020-0190(89)90122-1 |
| Reference:
|
[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 3824288 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[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 1316447 |
| Reference:
|
[28] Cho, H. G.: On the expected number of common edges in Delaunay and greedy triangulation.. Journal WSCG 5 (1997), 50–59. |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[31] Kirkpatrick, D. G.: A note on Delaunay and optimal triangulations.. Inform. Process. Lett. 10 (1980), 127–128. MR 0566856, 10.1016/0020-0190(80)90062-9 |
| Reference:
|
[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. MR 2148555, 10.1016/j.cag.2004.06.009 |
| Reference:
|
[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. MR 2148555, 10.1016/j.parco.2005.02.010 |
| Reference:
|
[34] Kolingerová, I.: Greedy triangulation improvement over lookahead search.. In: Computer Engineering and Informatics ’99 Proceedings, STU, Košice, 1999, 34–39. |
| Reference:
|
[35] Kolingerová, I., Dolák, M., Strych, V.: Eliminating contour line artefacts by using constrained edges.. Comput. Geosci. 35 (2009), 1975–1987. 10.1016/j.cageo.2008.12.017 |
| Reference:
|
[36] Kolingerová, I., Ferko, A.: Multicriteria-optimized triangulations.. Visual Comput. 17 (2001), 380–395. 10.1007/s003710100125 |
| Reference:
|
[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 3863318 |
| Reference:
|
[38] Krznaric, D.: Progress in hierarchical clustering & minimum weight triangulation.. PhD Thesis. University of Lund, Sweden, 1997. |
| Reference:
|
[39] Lawson, C. L.: Transforming triangulations.. Discrete Math. 3 (1972), 365–372. MR 0311491, 10.1016/0012-365X(72)90093-3 |
| Reference:
|
[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 0474682 |
| Reference:
|
[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. |
| Reference:
|
[42] Levcopoulos, Ch.: An $\Omega (\sqrt{n})$ lower bound for the nonoptimality of the greedy triangulation.. Inform. Process. Lett. 2 (1987), 247–251. MR 0896144, 10.1016/0020-0190(87)90170-0 |
| Reference:
|
[43] Levcopoulos, Ch., Krznaric, D.: The greedy triangulation can be computed from the Delaunay triangulation in linear time.. Comput. Geom. 14 (1999), 197–220. MR 1733811, 10.1016/S0925-7721(99)00037-1 |
| Reference:
|
[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 1076031 |
| Reference:
|
[45] Lingas, A.: The greedy and Delaunay triangulations are not bad in the average case.. Inform. Process. Lett. 22 (1986), 25–31. MR 0825643, 10.1016/0020-0190(86)90038-4 |
| Reference:
|
[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 1024851 |
| Reference:
|
[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 3399985 |
| Reference:
|
[48] Magová, I., Ferko, A., Niepel, L.: On edges elimination for the shortest mesh.. Journal WSCG 5 (1997), 396–403. |
| Reference:
|
[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. MR 0537055, 10.1016/0020-0190(79)90104-2 |
| Reference:
|
[50] Manacher, G. K., Zobrist, A. L.: Probabilistic methods with heaps for fast-average-case greedy algorithms.. Adv. Comput. Res. 1 (1983), 261–278. |
| Reference:
|
[51] Mulzer, W., Rotte, G.: Minimum-weight triangulation is NP-hard.. J. ACM 55 (2008), article no. 11, 29 pages. MR 2417038, 10.1145/1346330.1346336 |
| Reference:
|
[52] Okabe, A., Boots, B., Sugihara, K.: Spatial tesselations: concepts and applications of Voronoi diagrams.. John Wiley, Chichester, 1992. MR 1210959 |
| Reference:
|
[53] O'Rourke, J.: Computational geometry in C.. Cambridge University Press, New York, 1994. MR 1269320 |
| Reference:
|
[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. MR 2389937, 10.1016/j.cagd.2007.07.002 |
| Reference:
|
[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. |
| Reference:
|
[56] Pilz, A.: Flip distance between triangulations of a planar point set is APX-hard.. Comput. Geom. 47 (2014), 589–604. MR 3164111, 10.1016/j.comgeo.2014.01.001 |
| Reference:
|
[57] Preparata, F. P., Shamos, M. I.: Computational geometry: an introduction.. Springer, Heidelberg, 1985. MR 1004870, 10.1007/978-1-4612-1098-6 |
| Reference:
|
[58] Puppo, E., Davis, L. S., DeMenthon, D., Teng, A.: Parallel terrain triangulation.. Int. J. Geogr. Inf. Syst. 8 (1994), 105–128. 10.1080/02693799408901989 |
| Reference:
|
[59] Vomáčka, T., Kolingerová, I., Maňák, M.: Kinetic locally minimal triangulation: theoretical evaluation and combinatorial analysis.. Visual Comput. 36 (2020), 757–765. 10.1007/s00371-019-01657-y |
| Reference:
|
[60] Yu, X., Morse, B. S., Sederberg, T. W.: Image reconstruction using data-dependent triangulation.. IEEE Comput. Graph. 21 (2001), 62–68. 10.1109/38.920628 |
| . |
