Simulated Annealing and Genetic Algorithms in Quest of Optimal Triangulations

1. Acikgoz, N., Bottaso, C.L.: Metric-driven mesh optimization using a local simulated annealing algorithm. International Journal for Numerical Methods in Engineering 71, 201–223 (2007)

   Article  MathSciNet  Google Scholar 

2. Bartánus, M., Ferko, A., Mag, R., Niepel, L., Plachetka, T., Sikudová, E.: New heuristics for minimum weight triangulation. In: Proceedings from the 4th International Conference in Central Europe on Computer Graphics and Visualization 1996, pp. 31–40. University of West Bohemia, Pilsen (1996)

   Google Scholar 

3. Bærentzen J.A.: Optimizing 3D triangulations to recapture sharp edges. IMM-Technical Report-2006-11 (2006)

   Google Scholar 

4. Bobáková, G., Ferko, A., Niepel, L.: On minimum weight triangulation. In: Proceedings of the 10th International Conference Spring School of Computer Graphics, Bratislava, pp. 226–232 (1994)

   Google Scholar 

5. Bottaso, C.L.: Anisotropic mesh adaptation by metric-driven optimization. International Journal for Numerical Methods in Engineering 60, 597–639 (2004)

   Article  MathSciNet  Google Scholar 

6. Bremer, P.T., Hamann, B., Kreylos, O., Wolter, F.E.: Simplification of closed triangulated surfaces using simulated annealing. In: Lynch, T., Schumaker, L.L. (eds.) Mathematical methods in CAGD, pp. 1–8 (2001)

   Google Scholar 

7. Capp, C., Julstrom, B.A.: A weight-coded genetic algorithm for the minimum weight triangulation problem. In: Proceedings of the 1998 ACM Symposium on Applied Computing, pp. 327–331. New York (1998)

   Google Scholar 

8. Cazals, F., Giesen, J.: Delaunay Triangulation Based Surface Reconstruction. In: Boissonnat, J.-D., Teillaud, M. (eds.) Effective Computational Geometry for Curves and Surfaces, pp. 231–276. Springer, Heidelberg (2006)

   Chapter  Google Scholar 

9. Chen, K.C., Hsieh, I., Wang, C.A.: A genetic algorithm for minimum tetrahedralization of a convex polyhedron. In: Proceedings of the Canadian conference on computational geometry, Halifax, Nova Scotia, pp. 1–5 (2003)

   Google Scholar 

10. Chen, Y.H., Wang, Y.Z.: Genetic algorithms for optimized re-triangulation in the context of reverse engineering. Computer-Aided Design 31, 261–271 (1999)

    Article  MATH  Google Scholar 

11. Chetverikov, D., Stepanov, D., Krsek, P.: Robust Euclidean alignment of 3D point sets: the Trimmed Iterative Closest Point algorithm. Image and Vision Computing 23, 299–309 (2005)

    Article  Google Scholar 

12. Chetverikov, D., Jankó, Z., Lomonosov, E., Ekárt, A.: Creating photorealistic models by data fusion with genetic algorithms. In: A chapter of the edited volume Soft Computing in Image Processing: Recent Advances. Studies in Fuzziness and Soft Computing, vol. 210, pp. 239–266. Springer, Heidelberg (2007)

    Google Scholar 

13. Cignoni, P., Montani, C., Scopigno, R.: A merge-first divide & conquer algorithm for E^d Delaunay triangulations, Internal Rep. C92/16, CNUCE/CNR, Pisa, Italy (1992)

    Google Scholar 

14. Cooper, O., Campbell, N., Gibson, D.: Automatic augmentation and meshing of sparse 3D scene structure. In: Proceedings of the 7th IEEE workshop on applications of computer vision, pp. 287–293, Breckenridge (2005)

    Google Scholar 

15. Eppstein, D., Paterson, M.S., Yao, F.: On nearest-neighbor graphs. Discrete and Computational Geometry 17(3), 263–282 (1997)

    Article  MATH  MathSciNet  Google Scholar 

16. Goffe, W.L., Ferrier, G.D., Rogers, J.: Global optimization of statistical functions with simulated annealing. Journal of Econometrics 60, 65–100 (1994)

    Article  MATH  Google Scholar 

17. Goldberg, P.D.: Genetic algorithms in search, optimization and machine learning. Addison-Wesley Pub., Reading (1989)

    MATH  Google Scholar 

18. Holder, M., Karr, C.L.: Quadrilateral mesh smoothing using a steady state genetic algorithm. In: Cantú-Paz, E., Foster, J.A., Deb, K., Davis, L., Roy, R., O’Reilly, U.-M., Beyer, H.-G., Kendall, G., Wilson, S.W., Harman, M., Wegener, J., Dasgupta, D., Potter, M.A., Schultz, A., Dowsland, K.A., Jonoska, N., Miller, J., Standish, R.K. (eds.) GECCO 2003. LNCS, vol. 2724, pp. 2400–2401. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

19. Jankó, Z., Chetverikov, D., Ekárt, A.: Using genetic algorithms in computer vision: Registering images to 3D surface model. Acta Cybernetica 18, 193–212 (2007)

    MATH  Google Scholar 

20. Kallman, M.: Path planning in triangulations. In: Proceedings of the Workshop on Reasoning, Representation and Learning in Computer Games. In: International Joint Conference on Artficial Intelligence (IJCAI), Edinburg, Scotland, pp. 49–54 (2005)

    Google Scholar 

21. Kirkpatrick, S., Gelatt, C.D., Vecchi, M.O.: Optimization by simulated annealing. Science 220, 671–680 (1983)

    Article  MathSciNet  Google Scholar 

22. Kolingerová, I.: Genetic optimization of the triangulation weight. In: Proceedings of the 2nd international conference Computer Graphics and Artificial Intelligence, Limoges, pp. 23–34 (1998)

    Google Scholar 

23. Kolingerová, I.: Genetic approach to triangulations. In: Proceedings of the 4th international conference Computer graphics and artificial intelligence, Limoges, pp. 11–23 (2000)

    Google Scholar 

24. Kolingerová, I.: Probabilistic methods for triangulated models. In: Proceedings of the 8th international conference on Computer Graphics and Artificial Intelligence, Limoges, pp. 93–106 (2005)

    Google Scholar 

25. Kolingerová, I., Ferko, A.: Multicriteria-optimized triangulations. The Visual Computer 17, 380–395 (2001)

    Article  MATH  Google Scholar 

26. Kreylos, O., Hamann, B.: On simulated annealing and the construction of linear spline approximations for scattered data. IEEE Transactions on Visualization and Computer Graphics 7, 17–31 (2001)

    Article  Google Scholar 

27. Lawson, C.L.: Software for C ¹ Surface interpolation. In: Price, J.R. (ed.) Mathematical Sofware III, pp. 161–194. Academic Press, New York (2007)

    Google Scholar 

28. Lehner, B., Umlauf, G., Hamann, B.: Image compression using data-dependent triangulations. In: Bebis, G., Boyle, R., Parvin, B., Koracin, D., Paragios, N., Tanveer, S.-M., Ju, T., Liu, Z., Coquillart, S., Cruz-Neira, C., Müller, T., Malzbender, T. (eds.) ISVC 2007, Part I. LNCS, vol. 4841, pp. 351–362. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

29. Lomonosov, E., Chetverikov, D., Ekárt, A.: Pre-registration of arbitrarily oriented 3D surfaces using a genetic algorithm, Pattern Recognition Letters. Special Issue on Evolutionary Computer Vision and Image Understanding 27, 1201–1208 (2006)

    Google Scholar 

30. Mallampati, D.R., Mutalik, P.P., Wainwright, R.L.: A parallel multi-phase implementation of simulated annealing for the travelling salesman problem. In: Proceedings of the 6th Distributed memory computing conference, pp. 488–491 (1991)

    Google Scholar 

31. Manacher, K., Zobrist, A.L.: Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation. Information Processing Letters 9(1), 31–34 (1979)

    Article  MATH  MathSciNet  Google Scholar 

32. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculation by fast computing machines. J. Chem. Phys. 21, 1087 (1953)

    Article  Google Scholar 

33. Michalewitz, Z.: Genetic algorithms + data structures = Evolution programs. Springer, Heidelberg (1996)

    Google Scholar 

34. Morris, D., Kanade, T.: Image-consistent surface triangulation, In: Proceedings of the IEEE conference on computer vision and pattern recognition, vol.1, pp. 332–338 (2000)

    Google Scholar 

35. Mulzer, W., Rote, G.: Minimum Weight Trianglation is NP-hard. In: Proceedings of the 22nd Annual Symposium on Computational Geometry, Sedona, Association for Computing Machinery, pp. 1–10 (2006)

    Google Scholar 

36. Mutalik, P.P., Knight, L.R., Blanton, J.L., Wainwright, R.L.: Solving combinatorial optimization problems using parallel simulated annealing and parallel genetic algorithms. In: Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990, pp. 1031–1038 (1992)

    Google Scholar 

37. Prestifilippo, G., Sprave, J.: Optimal triangulation by means of evolutionary algorithms. In: Genetic Algorithms in Engineering Systems: Innovations and Applications, GALESIA 1997, pp. 492–497 (1997)

    Google Scholar 

38. Rila, L., Constantinides, A.G.: Image coding using data-dependent triangulation. In: Digital Signal Processing Proceedings, vol.2, pp. 531–534 (1997)

    Google Scholar 

39. Renner, G., Ekárt, A.: Genetic algorithms in computer aided design. Computer-Aided Design 35, 709–726 (2003)

    Article  Google Scholar 

40. Schumaker, L.L.: Computing optimal triangulations using simulated annealing. Computer Aided Geometric Design 10, 329–345 (1993)

    Article  MATH  MathSciNet  Google Scholar 

41. Sen, S., Zheng, S.: Near-optimal triangulation of a point set by simulated annealing. In: Symposium on Applied Computing, pp. 1000–1008 (1992)

    Google Scholar 

42. Seneviratne, L.D., Ko, W.-S., Earles, S.W.E.: Triangulation-based path planning for a mobile robot. In: Journal Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science, Professional Engineering Publishing, vol. 211(5), pp. 365–371 (1997)

    Google Scholar 

43. Shikhare, D., Gopalsamy, S., Modur, S.P.: A two phase technique for optimal tessellation of complex geometric models. In: 8th International conference on engineering computer graphics and descriptive geometry (1998)

    Google Scholar 

44. Toussaint, G.T.: The relative neighbourhood graph of a finite planar set. Pattern Recognition 12, 261–268 (1980)

    Article  MATH  MathSciNet  Google Scholar 

45. Vigo, M., Pla, N., Cotrina, J.: Regular triangulations of dynamic sets of points. Computer Aided Geometric Design 19(2), 127–149 (2002)

    Article  MATH  MathSciNet  Google Scholar 

46. Wagner, T., Michelitsch, T., Sacharow, A.: On the design of optimisers for surface reconstruction. In: Genetic and Evolutionary Commputation Conference (GECCO 2007), pp. 2195–2202 (2007)

    Google Scholar 

47. Weinert, K.: Optimal surface reconstruction from digitized point data using CI methods. Technical Report CI5 /97, SFB 531, University of Dortmund (1997)

    Google Scholar 

48. Wu, Y., Wainwright, R.L.: Near-optimal triangulation of a point set using genetic algorithms. In: Proceedings of the 7th Oklahoma symposium on AI, pp. 122–131 (1993)

    Google Scholar 

49. Yu, X., Morse, B.S., Sederberg, T.W.: Image Reconstruction Using Data-Dependent Triangulation. IEEE Computer Graphics and Applications 21(3), 62–68 (2001)

    Google Scholar 

Download references