|
|||||
|
|
Triangulations intersect nicely |
|
| Authors: | O Aichholzer F Aurenhammer Siu-Wing Cheng N Katoh G Rote M Taschwer Yin-Feng Xu |
| Institution: | 1. Institute for Theoretical Computer Science, Graz University of Technology, Klosterwiesgasse 32/2, A-8010, Graz, Austria 2. Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong 3. Department of Management Science, Kobe University of Commerce, Gakuen-Nishimachi 8-2-1, Nishi-ku, 651-21, Kobe, Japan 4. Institut für Mathematik, Technische Universit?t Graz, Steyrergasse 30, A-8010, Graz, Austria 5. School of Management, Xi'an Jiaotong University, 710049, Xi'an Shaanxi, People's Republic of China |
| Abstract: | We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other triangulation or to an edge that crosses it. This theorem also holds for the triangles of the triangulations and in general independence systems. As an application, we give some lower bounds for the minimum-weight triangulation which can be computed in polynomial time by matching and network-flow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |