Anisotropic Path Problems
Event details
| Date | 17.06.2014 |
| Hour | 14:00 |
| Speaker | Siu-Wing CHENG, The Hong Kong University of Science and Technology, Hong Kong |
| Location | |
| Category | Conferences - Seminars |
Finding shortest paths is a classical geometric optimization problem, but relatively less is known about cost models that depend on the travel direction than the standard Euclidean case or the isotropic weighted region case. But there are daily examples in which travel direction does matter. For example, the strength and direction of wind, current, or other force field may need to be considered. When planning a roadway or hiking on a terrain, it may be impossible to ascend or descend along slopes that are too steep, and the cost of a subpath may depend on the its slope. In this talk, we discuss some of the algorithmic results that we obtained in recent years, including approximation algorithms for the anisotropic path problems in the plane, on a terrain, and on polyhedral surfaces. In particular, our results allow us to find an approximate shortest path on a terrain with gradient constraints and under cost functions that are linear combinations of path length and total ascent. This talk represents joint work with several collaborators, including Jiongxin Jin, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang.
Links
Practical information
- General public
- Free
Organizer
- Boi Faltings
Contact
- Sylvie Thomet