Una descomposición convexa

MARIO LOMELÍ-HARO^*, VERÓNICA BORJA M.,
J. ALEJANDRO HERNÁNDEZ T.

Universidad Tecnológica de la Mixteca, Instituto de Física y Matemáticas, Huajuapan de León, Oaxaca, México.

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

Palabras claves: Aristas girables en triangulaciones, descomposiciones convexas, triangulaciones
MSC2010: 68U05, 68R05, 68R10.

A convex decomposition

Abstract.. Given a point set P on the plane, a convex decomposition of P is a set  of convex polygons with vertices inP satisfying the following conditions: The union of all elements in  is the convex hull ofP, 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 elements. In this work we give a procedure to find a specific convex decomposition of P with at most elements.

Keywords: Flipping edges in triangulations, convex decompositions, triangulations.

Texto Completo disponible en PDF

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, McGrraw- Hill, 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 set of 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).

^*E-mail: lomeli@mixteco.utm.mx.
Recibido: 07 de diciembre de 2013, Aceptado: 06 de agosto de 2014.
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.