Revista Integración, temas de matemáticas.

Revista Integración, temas de matemáticas

Vol. 32 Núm. 2 (2014): Revista Integración, temas de matemáticas
Artículo Original

Una descomposición convexa

PDF HTML
  • 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

Publicado 2014-10-31

Palabras clave

  • Aristas girables en triangulaciones,
  • descomposiciones convexas,
  • triangulaciones.

Cómo citar

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

Resumen

Dada una colección P de puntos en el plano, una descomposición convexa de P es un conjunto de polígonos convexos con vértices en P que satisfacen lo siguiente: La unión de todos los elementos de es el cierre convexo de P, cada elemento de es vacío (no contiene a ningún otro elemento de P en su interior) y para cualesquiera 2 elementos diferentes en sus interiores son disjuntos (se intersecarán en a lo más una arista). Únicamente se sabe que existen descomposiciones convexas con a lo más 7n/5 elementos para toda colección de n puntos. En este trabajo diremos cómo obtener una descomposición convexa específica de P con a lo más 3n/2 elementos.

Para citar este artículo: M. Lomelí-Haro, V. Borja, J.A. Hernández, Una descomposición convexa, Rev. Integr. Temas Mat. 32 (2014), no. 2, 169-180.

PDF HTML

Descargas

Los datos de descargas todavía no están disponibles.

Referencias

  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).