Revista Integración, temas de matemáticas.

Revista Integración, temas de matemáticas

Vol. 32 No. 2 (2014): Revista Integración, temas de matemáticas
Research and Innovation Articles

A convex decomposition

PDF (Español (España)) HTML (Español (España))
  • Mario Lomelí-Haro,
  • Verónica Borja M.,
  • J. Alejandro Hernández T.
Mario Lomelí-Haro
Universidad Tecnológica de la Mixteca
Verónica Borja M.
Universidad Tecnológica de la Mixteca
J. Alejandro Hernández T.
Universidad Tecnológica de la Mixteca

Published 2014-10-31

Keywords

  • Flipping edges in triangulations,
  • convex decompositions,
  • triangulations.

How to Cite

Lomelí-Haro, M., Borja M., V., & Hernández T., J. A. (2014). A convex decomposition. Revista Integración, Temas De matemáticas, 32(2), 169–180. Retrieved from https://revistas.uis.edu.co/index.php/revistaintegracion/article/view/4381

Abstract

Given a point set P on the plane, a convex decomposition of P is a set of convex polygons with vertices in P satisfying the following conditions: The union of all elements in is the convex hull of P, every element in is empty (that is, they no contain any element of P in its interior), and any given 2 elements in its interiors are disjoint intersecting them in at most one edge. It is known that if P has n elements, then there exists a convex decomposition of P with at most 7n/5 elements. In this work we give a procedure to find a specific convex decomposition of P with at most 3n/2 elements.

To cite this article: M. Lomelí-Haro, V. Borja, J.A. Hernández, Una descomposición convexa, Rev. Integr. Temas Mat. 32 (2014), no. 2, 169-180.

 
PDF (Español (España)) HTML (Español (España))

Downloads

Download data is not yet available.

References

  1. Aichholzer O. and Krasser H., “The point set order type data base: A collection of applications and results”, in Proc. 13th Canadian Conference on Computational Geometry, Waterloo, Ontario, Canada, (2001), 17-20.
  2. Boná M., A Walk Through Combinatorics. An Introduction to Enumeration and Graph Theory, World Scientific, 2006.
  3. Cormen T., Leiserson C.E., Rivest R.L. and Stein C., Introduction to Algorithms, McGrrawHill, Boston, 2001.
  4. Erdös P. and Szekeres G., “A combinatorial problem in geometry”, Compositio Math. 2 (1935), 463-470.
  5. García-López J. and Nicolás C., “Planar point sets with large minimum convex partitions”, in Proc. 22nd Euro. Workshop on Comput. Geom., Delphi, Greece, (2006), 51-54.
  6. Galtier J., Hurtado F., Noy M., Pérennes S. and Urrutia J., “Simultaneous Edge Flipping in Triangulations”, Internat. J. Comput. Geom. Appl. 13 (2003), no. 2, 113-133.
  7. Gerken T., “Empty convex hexagons in planar point sets”, Discrete Comput. Geom. 39 (2008), no. 1-3, 239-272.
  8. Harborth H., “Konvexe Fünfecke in ebenen Punktmengen”, Elem. Math. 33 (1978), no. 5, 116-118.
  9. Horton J.D., “Sets with no empty convex 7-gons”, Canad. Math. Bull. 26 (1983), no. 4, 482-484.
  10. Hosono K., “On convex decompositions of a planar point set”, Discrete Math. 309 (2009), no. 6, 1714-1717.
  11. Neumann V., Rivera-Campo E. and Urrutia J., “A note on convex decompositions of a setof points in the plane”, Graphs Combin. 20 (2004), no. 2, 223-231.
  12. Overmars M., Finding sets of points without empty convex 6-gons, Discrete Comput. Geom. 29 (2003), 153–158.
  13. Tóth G. and Valtr P., “Note on the Erdös-Szekeres theorem”, Discrete Comput. Geom. 19 (1998), no. 3, 457-459.
  14. Urrutia J., “Open-problem session”, in 10th Canadian Conference on Computational Geometry, Montreal, Canada, (1998).