On Edge-Disjoint Empty Triangles of Point Sets

Javier Cano (), Luis F. Barba (), Toshinori Sakai () and Jorge Urrutia ()
Additional contact information
Javier Cano: Universidad Nacional Autónoma de México, Posgrado en Ciencia e Ingeniería de la Computación
Luis F. Barba: Universidad Nacional Autónoma de México, Posgrado en Ciencia e Ingeniería de la Computación
Toshinori Sakai: Tokai University, Research Institute of Educational Development
Jorge Urrutia: Universidad Nacional Autónoma de México, Instituto de Matemáticas

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 83-100 from Springer

Abstract: Abstract Let P be a set of points in the plane in general position. Any three points $$x,y,z \in P$$ determine a triangle $$\Delta (x,y,z)$$ of the plane. We say that $$\Delta (x,y,z)$$ is empty if its interior contains no element of P. In this chapter, we study the following problems: What is the size of the largest family of edge-disjoint triangles of a point set? How many triangulations of P are needed to cover all the empty triangles of P? We also study the following problem: What is the largest number of edge-disjoint triangles of P containing a point q of the plane in their interior? We establish upper and lower bounds for these problems.

Keywords: General Position; Complete Graph; Triple System; Regular Polygon; Geometric Graph (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_7

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().