When solving technical problems in computer graphics and visualization, we often have to tackle hard optimization problems that lead to a combinatorial explosion. A genetic algorithm is one of the well-known heuristic that allows us to search for satisfactory solutions to such hard problems, by mimicing the process of natural evolution.
I will talk about two optimization and search problems and how we can solve these problems by employing genetic-based approaches. The first problem is to find an optimal placement of annotation labels around the metro network, which enables the automatic generation of annotated metro maps. The second problem is to unfold a 3D polygonal object into a single-connected patch so that we can fully facilitate the manual construction of the corresponding papercraft models. Several examples will be also provided to demonstrate that genetic-based evolutional computation effectively search for plausible solutions even in a large search space once we can successfully encode such solutions using genetic representations.
Shigeo Takahashi received his BS, MS., and PhD degrees in computer science from the University of Tokyo in 1992, 1994, and 1997, respectively. He is currently an associate professor in the Graduate School of Frontier Sciences at the University of Tokyo, Japan. His research interests include computer visualization, visual perception modeling, geometric modeling, and geographical information systems. He is on the editorial boards for IEEE TVCG (2011-), and has served as a program committee member for more than 30 graphics and visualization conferences. He won the most cited paper award for the international journal Graphical Models 2004-2006.