Triangulations With Edge Criteria - Sleeping Beauties Rightly or Wrongly Forgotten?

Ivana Kolingerová

Pokroky matematiky, fyziky a astronomie (2020)

  • Volume: 65, Issue: 4, page 223-233
  • ISSN: 0032-2423

Abstract

top
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í.

How to cite

top

Kolingerová, Ivana. "Triangulace s hranovými kritérii - Šípkové Růženky právem nebo neprávem zapomenuté?." Pokroky matematiky, fyziky a astronomie 65.4 (2020): 223-233. <http://eudml.org/doc/297152>.

@article{Kolingerová2020,
abstract = {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í.},
author = {Kolingerová, Ivana},
journal = {Pokroky matematiky, fyziky a astronomie},
language = {cze},
number = {4},
pages = {223-233},
publisher = {Jednota českých matematiků a fyziků},
title = {Triangulace s hranovými kritérii - Šípkové Růženky právem nebo neprávem zapomenuté?},
url = {http://eudml.org/doc/297152},
volume = {65},
year = {2020},
}

TY - JOUR
AU - Kolingerová, Ivana
TI - Triangulace s hranovými kritérii - Šípkové Růženky právem nebo neprávem zapomenuté?
JO - Pokroky matematiky, fyziky a astronomie
PY - 2020
PB - Jednota českých matematiků a fyziků
VL - 65
IS - 4
SP - 223
EP - 233
AB - 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í.
LA - cze
UR - http://eudml.org/doc/297152
ER -

References

top
  1. Agarwal, P. K., Kaplan, H., Rubin, N., 10.1007/s00454-015-9729-3, . Discrete Comput. Geom. 54 (2015), 871–904. (2015) MR3416904DOI10.1007/s00454-015-9729-3
  2. Aichholzer, O., Aurenhammer, F., Cheng, S. W., Katoh, N., Rote, G., Taschwer, M., Xu, Y. F., 10.1007/BF02712872, . Discrete Comput. Geom. 16 (1996), 339–359. (1996) MR1414960DOI10.1007/BF02712872
  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. (1998) MR1688112
  4. Aurenhammer, F., 10.1145/116873.116880, . ACM Comput. Surv. 23 (1991), 345–405. (1991) DOI10.1145/116873.116880
  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. (1996) 
  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. (1998) 
  7. Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., Tan, T. S., 10.1007/BF02573962, . Discrete Comput. Geom. 10 (1993), 47–65. (1993) MR1215322DOI10.1007/BF02573962
  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. (1995) MR1239190
  9. de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O., 10.1007/978-3-662-03427-9_1, . Springer, Heidelberg, 1997. (1997) MR1470713DOI10.1007/978-3-662-03427-9_1
  10. Bose, P., Devroye, L., Evans, W., 10.1142/S0218195902000979, . Internat. J. Comput. Geom. 12 (2002), 445–454. (2002) MR1945593DOI10.1142/S0218195902000979
  11. Cignoni, P., Montani, C., Perego, R., Scopigno, R, Parallel 3D Delaunay triangulation, . In: Proc. of Eurographics ’93, 1993, C129–C142. (1993) 
  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. (1989) 
  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. (1994) MR1452410
  14. Dickerson, M. T., Keil, J. M., Montague, M. H., 10.1007/PL00009320, . Discrete Comput. Geom. 18 (1997), 289–304. (1997) MR1487646DOI10.1007/PL00009320
  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. (1996) 
  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. (1995) 
  17. Dyn, N., Levin, D., Rippa, S., 10.1093/imanum/10.1.137, . IMA J. Numer. Anal. 10 (1990), 137–154. (1990) MR1036653DOI10.1093/imanum/10.1.137
  18. Edelsbrunner, H., Tan, T. S., 10.1137/0222036, . SIAM J. Comput. 22 (1991), 527–551. (1991) MR1219039DOI10.1137/0222036
  19. Edelsbrunner, H., Tan, T. S., Waupotisch, R., 10.1137/0913058, . SIAM J. Stat. Sci. Comput. 13 (1992), 994–1008. (1992) MR1166172DOI10.1137/0913058
  20. Eppstein, D., 10.1016/0925-7721(92)90013-I, . Comp. Geom.-Theor. Appl. 1 (1992), 143–148. (1992) MR1154641DOI10.1016/0925-7721(92)90013-I
  21. Fang, Y., An improved Lawson local-optimization procedure and its applications, . TR, University of Victoria, 2018. (2018) 
  22. Gilbert, P. D., New results on planar triangulations, . Tech. Rep. ACT-15. Coord. Sci. Lab., University of Illinois, Urbana, 1979. (1979) 
  23. Goldman, S., 10.1016/0020-0190(89)90122-1, . Inform. Process. Lett. 32 (1989), 191–196. (1989) MR1000272DOI10.1016/0020-0190(89)90122-1
  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. (2018) MR3824288
  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. (1997) 
  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. (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. (1994) MR1316447
  28. Cho, H. G., On the expected number of common edges in Delaunay and greedy triangulation, . Journal WSCG 5 (1997), 50–59. (1997) 
  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. (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. (1999) 
  31. Kirkpatrick, D. G., 10.1016/0020-0190(80)90062-9, . Inform. Process. Lett. 10 (1980), 127–128. (1980) MR0566856DOI10.1016/0020-0190(80)90062-9
  32. Kohout, J., Kolingerová, I., Žára, J., 10.1016/j.cag.2004.06.009, . Comput. Graph. 28 (2004), 703–718. (2004) MR2148555DOI10.1016/j.cag.2004.06.009
  33. Kohout, J., Kolingerová, I., Žára, J., 10.1016/j.parco.2005.02.010, . Parallel Comput. 31 (2005), 491–522. (2005) MR2148555DOI10.1016/j.parco.2005.02.010
  34. Kolingerová, I., Greedy triangulation improvement over lookahead search, . In: Computer Engineering and Informatics ’99 Proceedings, STU, Košice, 1999, 34–39. (1999) 
  35. Kolingerová, I., Dolák, M., Strych, V., 10.1016/j.cageo.2008.12.017, . Comput. Geosci. 35 (2009), 1975–1987. (2009) DOI10.1016/j.cageo.2008.12.017
  36. Kolingerová, I., Ferko, A., 10.1007/s003710100125, . Visual Comput. 17 (2001), 380–395. (2001) DOI10.1007/s003710100125
  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. (2018) MR3863318
  38. Krznaric, D., Progress in hierarchical clustering & minimum weight triangulation, . PhD Thesis. University of Lund, Sweden, 1997. (1997) 
  39. Lawson, C. L., 10.1016/0012-365X(72)90093-3, . Discrete Math. 3 (1972), 365–372. (1972) MR0311491DOI10.1016/0012-365X(72)90093-3
  40. Lawson, C. L., Software for C1 surface interpolation, . In: Rice, J. R. C.: Mathematical Software III, Academic Press, New York, 1977, 161–194. (1977) MR0474682
  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. (1997) 
  42. Levcopoulos, Ch., 10.1016/0020-0190(87)90170-0, . Inform. Process. Lett. 2 (1987), 247–251. (1987) MR0896144DOI10.1016/0020-0190(87)90170-0
  43. Levcopoulos, Ch., Krznaric, D., 10.1016/S0925-7721(99)00037-1, . Comput. Geom. 14 (1999), 197–220. (1999) MR1733811DOI10.1016/S0925-7721(99)00037-1
  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. (1990) MR1076031
  45. Lingas, A., 10.1016/0020-0190(86)90038-4, . Inform. Process. Lett. 22 (1986), 25–31. (1986) MR0825643DOI10.1016/0020-0190(86)90038-4
  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. (1988) MR1024851
  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. (2012) MR3399985
  48. Magová, I., Ferko, A., Niepel, L., On edges elimination for the shortest mesh, . Journal WSCG 5 (1997), 396–403. (1997) 
  49. Manacher, G. K., Zobrist, A. L., 10.1016/0020-0190(79)90104-2, . Inform. Process. Lett. 9 (1979), 31–34. (1979) MR0537055DOI10.1016/0020-0190(79)90104-2
  50. Manacher, G. K., Zobrist, A. L., Probabilistic methods with heaps for fast-average-case greedy algorithms, . Adv. Comput. Res. 1 (1983), 261–278. (1983) 
  51. Mulzer, W., Rotte, G., 10.1145/1346330.1346336, . J. ACM 55 (2008), article no. 11, 29 pages. (2008) MR2417038DOI10.1145/1346330.1346336
  52. Okabe, A., Boots, B., Sugihara, K., Spatial tesselations: concepts and applications of Voronoi diagrams, . John Wiley, Chichester, 1992. (1992) MR1210959
  53. O'Rourke, J., Computational geometry in C, . Cambridge University Press, New York, 1994. (1994) MR1269320
  54. Osherovich, E., Bruckstein, M. M., 10.1016/j.cagd.2007.07.002, . Comput. Aided Geom. Design 25 (2008), 157–161. (2008) MR2389937DOI10.1016/j.cagd.2007.07.002
  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. (2003) 
  56. Pilz, A., 10.1016/j.comgeo.2014.01.001, . Comput. Geom. 47 (2014), 589–604. (2014) MR3164111DOI10.1016/j.comgeo.2014.01.001
  57. Preparata, F. P., Shamos, M. I., 10.1007/978-1-4612-1098-6, . Springer, Heidelberg, 1985. (1985) MR1004870DOI10.1007/978-1-4612-1098-6
  58. Puppo, E., Davis, L. S., DeMenthon, D., Teng, A., 10.1080/02693799408901989, . Int. J. Geogr. Inf. Syst. 8 (1994), 105–128. (1994) DOI10.1080/02693799408901989
  59. Vomáčka, T., Kolingerová, I., Maňák, M., 10.1007/s00371-019-01657-y, . Visual Comput. 36 (2020), 757–765. (2020) DOI10.1007/s00371-019-01657-y
  60. Yu, X., Morse, B. S., Sederberg, T. W., 10.1109/38.920628, . IEEE Comput. Graph. 21 (2001), 62–68. (2001) DOI10.1109/38.920628

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.