×

Bichromatic quadrangulations with Steiner points. (English) Zbl 1118.52018

Summary: Let \(P\) be a \(k\)-colored point set in general position, \(k \geq 2\). A family of quadrilaterals with disjoint interiors \(\mathcal Q_1, \ldots, \mathcal Q_m\) is called a quadrangulation of \(P\) if \(V(\mathcal Q_1) \cup \cdots \cup V(\mathcal Q_m) = P\), the edges of all \(\mathcal Q_i\) join points with different colors, and \(\mathcal Q_1 \cup \cdots \cup \mathcal Q_m =\text{Conv} (P)\).
In general it is easy to see that not all \(k\)-colored point sets admit a quadrangulation; when they do, we call them quadrangulatable. For a point set to be quadrangulatable it must satisfy that its convex hull Conv(\(P\)) has an even number of points and that consecutive vertices of Conv(\(P\)) receive different colors. This will be assumed from now on.
In this paper, we study the following type of questions: Let \(P\) be a \(k\)-colored point set. How many Steiner points in the interior of Conv(\(P\)) do we need to add to \(P\) to make it quadrangulatable? When \(k = 2\), we usually call \(P\) a bichromatic point set, and its color classes are usually denoted by \(R\) and \(B\), i.e. the red and blue elements of \(P\). In this paper, we prove that any bichromatic point set \(P = R\cup B\) where \(| R | = | B | = n\) can be made quadrangulatable by adding at most \(\left\lfloor\frac{n -1}{3}\right\rfloor + \left\lfloor\frac{n}{2}\right\rfloor + 1\) Steiner points and that \(\frac{m}{3}\) Steiner points are occasionally necessary. To prove the latter, we also show that the convex hull of any monochromatic point set \(P\) of \(n\) elements can be always partitioned into a set \({\mathcal{S}} = \{{\mathcal{S}}_1,\dots, {\mathcal{S}}_{t}\}\) of star-shaped polygons with disjoint interiors, where \(V({\mathcal{S}}_1)\cup\cdots\cup V({\mathcal{S}}_{t})= P\) and \(t\leq \left\lfloor\frac{n - 1}{3}\right\rfloor+1\). For \(n = 3 k\) this bound is tight. Finally, we prove that there are 3-colored point sets that cannot be completed to 3-quadrangulatable point sets.

MSC:

52A99 General convexity
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, A., Murty, U. S. R.: Graph Theory with Applications, Elsevier Science Publishing, New York (1976) · Zbl 1226.05083
[2] Bose, P., Toussaint, G.: Characterizing and efficiently computing quadrangulations of planar point sets. Comput. Aided Geom. Des. 14, 763–785 (1997) · Zbl 0893.68153
[3] Bremner, D., Hurtado, F., Ramaswami, S., Sacristán, V.: Small convex quadrangulations of point sets. Algorithmica 38(2), 317–339 (2003) · Zbl 1072.68120
[4] Cortés, C., Márquez, A., Nakamoto, A., Valenzula, J.: Quadrangulations and 2-colorations. 21st European Workshop on Computational Geometry, pp. 65–68. Eindhoven, March 9–11, 2005
[5] Fisk, S.: A short proof of Chvátal’s watchman theorem. J. Comb. Theory B 24, 374 (1978) · Zbl 0376.05018
[6] Heredia, M., Urrutia, J.: On convex quadrangulations of point sets on the plane. Discrete geometry, Combinatorics and Graph Theory, Lecture Notes in Computer Science 4381, 38–46 (2007) · Zbl 1149.52301
[7] Lai, M. L., Schumaker, L. L.: Scattered data interpolation using piecewise polynomials of degree six. SIAM J. Numer. Anal. 34, 905–921 (1997) · Zbl 0872.41004
[8] Ramaswami, S., Ramos, P., Toussaint, G.: Converting triangulations to quadrangulations. Comput. Geom. Theory Appl. 9, 257–276 (1998) · Zbl 0894.68158
[9] Sperner, E.: Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes. Hambg. Abhand. 6, 265–272 (1928). · JFM 54.0614.01
[10] Toussaint, G.: Quadrangulations of planar sets. In: Proceedings of the 4th International Workshop on Algorithms and Data Structures, pp. 218–227. Springer, Berlin (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.