|
|||||
|
|
On the Number of Edges in Geometric Graphs Without Empty Triangles |
|
| Authors: | C. Bautista-Santiago M. A. Heredia C. Huemer A. Ramírez-Vigueras C. Seara J. Urrutia |
| Affiliation: | 1. Universidad Autónoma Metropolitana, Unidad Azcapotzalco, Mexico City, Mexico 2. Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México, Mexico City, Mexico 3. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Barcelona, Spain 4. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain 5. Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico City, Mexico |
| Abstract: | In this paper we study the extremal type problem arising from the question: What is the maximum number ET(S) of edges that a geometric graph G on a planar point set S can have such that it does not contain empty triangles? We prove: ${{n choose 2} - O(n log n) leq ET(n) leq {n choose 2} - left(n - 2 + leftlfloor frac{n}{8} rightrfloor right)}$ . |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |