On three parameters of invisibility graphs

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 On three parameters of invisibility graphs ∗ Josef Cibulka † 1 , Miroslav Korbelá° ‡ 2 , Jan Kyn£l § 1 , Viola Mészáros ¶ 3 , Rudolf Stola° k 1 , and Pavel Valtr ∗∗ 1 1 Department of Applied Mathematis and Institute for Theoretial Computer Siene, Charles University, Faulty of Mathematis and Physis, Malostranské nám. 25, 118 00 Prague, Czeh Republi 2 Department of Mathematis and Statistis, Faulty of Siene, Masaryk University, Kotlá°ská 2, 611 37 Brno, Czeh Republi 3 Institute for Mathematis, Tehnial University of Berlin, Strasse des 17. Juni 136, 10623 Berlin, Germany Abstrat The invisibility graph I(X) of a set X⊆Rd is a (p ossibly innite) graph whose verties are the p oints of X and two verties are onneted by an edge if and only if the straight-line segment onneting the two orresp onding p oints is not fully ontained in X . We onsider the following three parameters of a set X : the lique number ω(I(X)) , the hromati numb er χ(I(X)) and the minimum numb er γ(X) of onvex subsets of X that over X . We settle a onjeture of Matou²ek and Valtr laiming that for every planar set X , γ(X) an b e b ounded in terms of χ(I(X)) . As a part of the pro of we show that a dis with n one-p oint holes near its b oundary has χ(I(X)) ≥log log(n) but ω(I(X)) = 3 . We also nd sets X in R5 with χ(I(X)) = 2 , but γ(X) arbitrarily large. 1 Intro dution Let X b e a subset of a d -dimensional Eulidean spae. We say that two p oints x, y ∈X see eah other if the straight-line segment xy onneting x and y is a subset of X . The invisibility graph I(X) of a set ∗ This researh was supported by the pro jet CE-ITI (GACR P202/12/G061) of the Czeh Siene Foundation and by the grant SVV-2013-267313 (Disrete Mo dels and Algorithms). The seond author was supported by the pro jet CZ.1.07/2.3.00/20.0003 of the Op erational Programme Eduation for Comp etitiveness of the Ministry of Eduation, Youth and Sp orts of the Czeh Republi. The fourth author was also partially supp orted by ESF EuroGiga pro jet ComPoSe (IP03), by OTKA Grant K76099 and by OTKA Grant 102029. The rst, the third and the sixth author were partially supp orted by pro jet GAUK 52410. Part of the researh was onduted during the Speial Semester on Disrete and Computational Geometry at Éole Polytehnique Féderale de Lausanne, organized and supp orted by the CIB (Centre Interfaultaire Bernoulli) and the SNSF (Swiss National Siene Foundation). † Email: ibulkakam.m.uni.z. ‡ Email: miroslav.korb elargmail.om. § Email: kynlkam.m.uni.z. ¶ Email: meszarosmath.tu-b erlin.de. k Email: rudakam.m.uni.z. ∗∗ Email: valtrkam.m.uni.z. X⊆Rd is a graph whose verties are the p oints of X and two verties are onneted by an edge if and only if they do not see eah other. Let χ(G) b e the hromati numb er of a graph G and let ω(G) b e its lique numb er. For a set X⊆Rd we dene γ(X) to b e the minimum p ossible numb er of onvex subsets of X that over X . Further, let χ(X) := χ(I(X)) and ω(X) := ω(I(X)) . Sets X with ω(X) = n−1 are sometimes alled n -onvex [8℄. Observe that ω(X)≤χ(X)≤γ(X) for any set X . If a planar set X is losed, then γ(X) an b e b ounded by a funtion of ω(X) . This was proved by Breen and Kay [2℄ and the urrent best known upp er b ound is γ(X)≤O(ω(X)3) by Matou²ek and Valtr [6℄. From the other diretion, there exist examples by Matou²ek and Valtr [6℄ with γ(X)≥ Ω(ω(X)2 ). However, if we don't restrit ourselves to losed sets, there is no upp er b ound on γ(X) even for sets with ω(X) = 3 . An example is the dis Dλ with λ one-p oint holes puntured in the verties of a regular onvex λ -gon near the b oundary of Dλ , for whih ω(Dλ) = 3 , but γ(Dλ) = ⌈λ/2⌉+ 1 (see [6℄). A one-point hole in a set X⊂Rd is a p oint that forms a path-onneted omp onent of Rd\X . Let λ(X) b e the numb er of one-p oint holes in the set X . The example of the set Dλ led to studying the properties of planar sets with a limited numb er of onep oint holes by Matou²ek and Valtr [6℄. In partiular, they proved the following theorem. Theorem 1 (Matou²ek and Valtr [6℄) Let X⊆ R2 be a set with ω(X) = ω < ∞ and λ(X) = λ < ∞ . Then γ(X)≤O(ω4+λω2). For any ω≥3 and λ≥0 they also found sets X with ω(X) = ω , λ(X) = λ and γ(X)≥Ω(ω3+ωλ) . Matou²ek and Valtr [6℄ onjetured that for an arbitrary planar set X , the value of γ(X) is b ounded by a funtion of χ(X) . Then χ(X) annot be b ounded 103 On three parameters of invisibility graphs by a funtion of ω(X) as shows the ab ove example with Dλ . Lawrene and Morris [4℄ proved that for every k there exists n0(k) suh that whenever S is a set of nitely many points in the plane and |S| ≥ n0(k) , then χ(R2\S)≥k . 1 Thus, whenever X is the omplement of a nite set of p oints, λ(X) an b e b ounded in terms of χ(X) . This implies, by Theorem 1, that the value of γ(X) an b e b ounded in terms of χ(X) , settling the onjeture of Matou²ek and Valtr in the sp eial ase when X is a omplement of a nite set of p oints. In this pap er, we strengthen the result of Lawrene and Morris [4℄ and settle the onjeture for every planar set X . The tower funtion Tl(k) is dened reursively as T0(k) = k and Th(k) = 2Th−1(k) . Its inverse is the iterated logarithm log(l)(n) , that is, log(0)(n) = n and log(l)(n) = log(log(l−1)(n)) . Theorem 2 Any set X⊆R2 with χ(X) = χ < ∞ satises γ(X)≤O(24T2(χ)·χ3). The pro of of Theorem 2 is omitted from this extended abstrat. In the full version of the paper, we also show that for every dimension d , λ(X) an b e b ounded in terms of χ(X) for sets X⊂Rd . This answers Question 6 of Lawrene and Morris [4℄. A set X is star-shaped if X ontains a p oint x∈X that sees every other p oint of X . In Setions 2 and 3 we show that χ and γ an b e separated in dimensions 5 and more. Theorem 3 For every positive integer g there exist star-shaped sets 1. X⊂R6 satisfying χ(X) = 2 and γ(X)≥g and 2. Xc⊂R6 that is losed and satises χ(Xc) = 4 and γ(Xc)≥g . Theorem 4 For every positive integer g there exist star-shaped sets 1. X⊂R5 satisfying χ(X) = 2 and γ(X)≥g and 2. Xc⊂R5 that is losed and satises χ(Xc) = 6 and γ(Xc)≥g . Problem 1 Does there exist a funtion f suh that γ(X)≤f(χ(X)), 1. for every set X⊆R3 ? 2. for every set X⊆R4 ? All logarithms in this pap er are binary. We use the notation xy for the straight line segment b etween p oints x and y . 1 The graph GS in the pap er of Lawrene and Morris is pre- isely the invisibility graph of R2\S . 2 Construtions in dimension 6 2.1 Set with hromati numb er 2 We prove part 1 of Theorem 3. Part 2 is omitted from this extended abstrat. Let Pn b e the yli polytope on n≥7 verties (see for example [5℄) and Vn its set of verties. Thus the onvex hull of every triple of points from Vn is a triangular fae of Pn . Lemma 5 Let Kn be the omplete graph on the set V of n≥7 verties and let k:= ⌈2 log(n) + 2⌉ . It is possible to orient the edges of Kn so that every set V′⊆V of size at least k ontains a direted triangle. Pro of. For brevity, we all a set V′ good if it ontains a direted triangle. We orient the edges randomly and show that with p ositive probability, every set V′⊆V of size at least k is go o d. First, we will b ound the probability bk that a given set V′ of k verties is bad. If there exists a direted yle on V′ of length greater than 3 , then one of the two yles reated by adding an arbitrary diagonal to the yle is again direted. Thus there exists a direted triangle on V′ . There are 2k(k−1)/2 p ossible orientations of edges of a omplete graph on k verties out of whih k! are ayli. Thus bk=k! 2k(k−1)/2=k!2−k2/2+k/2. The probability that some k -tuple V′ of verties is bad is thus at most n kbk≤nk k!bk= 2klog(n)−k2/2+k/2= = 2k(log(n)−k/2+1/2) ≤ ≤2k(log(n)−log(n)−1+1/2) ≤2k(−1/2) <1.  We x the orientation of the edges of Pn in whih every k -tuple of verties is go o d. A triangular fae of Pn has direted boundary if the three edges of the fae form a direted yle. The set X is onstruted by punturing a one-p oint hole in the baryenter of triangular faes of Pn with direted b oundary. Verties of Pn are olored blak. Edges are ut in thirds. In every edge, the interior of the middle third together with the point at one third loser to the end of the edge is olored white. The rest of the edges is blak. The oloring of triangular faes with direted b oundary is depited on Fig. 1. The rest of X is olored blak. All the edges of the invisibility graph of X are b etween pairs of points lying on the same triangular fae 104 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 vivj vk p1p2 p3 p4 p5 p6 Figure 1: Coloring of a fae with direted b oundary. Lines determined by pairs (p1, p4) , (p2, p5) and (p3, p6) interset in the baryenter and split the triangle into mono hromati regions. Full lines and gray areas represent blak olor, the rest is white. with direted b oundary. The oloring is proper on eah of these faes and thus the 2 -oloring of the whole X is prop er. If a onvex set C ontains at least k verties of X , then it ontains a triangular fae with direted b oundary and thus C ontains a one-p oint hole. Therefore γ(X)≥n 2 log(n) + 3. 3 Construtions in dimension 5 Here we present some parts of the pro of of part 1 of Theorem 4. The rest of the pro of is omitted from this extended abstrat. The onstrutions are similar to those in dimension 6 : for part (1) of the theorem, the set X is a losed yli polytop e with one-p oint holes in some of the 2 -dimensional faes. For part (2), instead of p oints we remove small 5 -dimensional p olytop es attahed to the 2-dimensional faes. The dierene from the onstrution in dimension 6 is in the plaement of the holes: here we annot apply the same argument as in the previous setion sine for the yli p olytop e in dimension 5 only quadratially many triples of verties indue a 2 -dimensional fae and there is a 2 -oloring of the vertex set in whih no 2 -dimensional fae is mono hromati. In the full version of the paper, we show two different ways how to hoose the holes. In the rst onstrution we essentially show that randomly hosen holes will do, but the proof (interestingly) requires a rather nontrivial result from group theory. Also the onstrution proves only part (1) of the theorem. In the seond onstrution we sp eify the lo ations of the holes preisely. Moreover, we show that the holes an b e enlarged to op en pyramids, whih shows part (2) of the theorem. The pro of of part (2) of the theorem is analogous to the pro of of part (2) of Theorem 3 and is omitted from this abstrat. Let Pn b e the 5 -dimensional yli p olytop e on n≥6 verties with (ordered) vertex set Vn= {v1, v2,...,vn} . For brevity, we all the triangular fae with verties vi , vj and vk the ijk triangle. Similarly, the ij edge is the edge b etween verties vi and vj . The 2 -dimensional faes of Pn are the triangles •1ij for every 1< i < j ≤n (typ e 1ij triangles), •ijn for every 1≤i < j < n (typ e ijn triangles), •i(i+1)j for every 1< i < j−1< n (typ e i(i+1)j triangles) and •ij(j+1) for every 1< i < j < n−1 (typ e ij(j+1) triangles). 3.1 Covering with onvex sets In the onstrutions proving part (1) of Theorem 4, we remove a one-p oint hole from every type 1ij triangle. In the onstrution proving part (2), we remove an op en at simplex instead of the p oint (as in Setion 2). The following lemma shows that in b oth ases, the resulting set an not b e overed by a b ounded numb er of onvex sets. Lemma 6 Let X be a subset of Pn suh that every edge of Pn is a subset of X and none of the type 1ij triangles is a subset of X . Then γ(X)≥ Ω(log n/ log log n) . Pro of. Let X=C1∪C2∪ · · · ∪ Ck b e a overing of X with onvex subsets of X . The overing indues a partition of eah open edge 1i , 2≤i≤n , into at most k intervals I1 i, I2 i,...,Iki i , where eah of the intervals Ij i is overed by one of the onvex sets Cl(i,j) . Sine the onvex sets in the overing may overlap, this partition need not be unique; in suh a ase we just pik one. We say that the partitions of two edges 1i and 1i′ are of the same type if ki=ki′ , l(i, p) = l(i′, p) for eah p= 1,2,...,ki (in other words, the olors app ear in the same order along the edges), and for eah p= 1,2,...,ki the typ e of the interval Ip i (that is, losed, open, or half-losed from the left/right) is the same as the typ e of the interval Ip i′ . Degenerate onep oint intervals are onsidered as losed. The numb er of typ es of the partitions is at most 2k·k!·2k−1 . Indeed, there are at most 2k subsets of olors, eah of the subsets an b e linearly ordered in at most k! ways, and there are at most k−1 b oundary p oints shared by two intervals, where one of the intervals is lo ally losed and the other one lo ally op en. It follows that if n > 2k·k!·2k−1+ 1 , then there are two edges 1i and 1i′ of the same typ e. The onvex hulls conv(Ip i∪Ip i′) over the whole op en triangle 1ii′ , inluding the one-p oint hole inside, whih is a ontradition. Therefore n≤2k·k!·2k−1+ 1 , whih implies that γ(X)≥Ω(log n/ log log n) .  105 On three parameters of invisibility graphs 4 Conluding remarks To solve Problem 1 in dimension 4 we ould use a onstrution similar to those in dimensions 5 and 6 provided the following problem has a p ositive answer. Problem 2 Does there exist for every k a onvex simpliial polytope P(k) in R4 suh that in every oloring of verties of P(k) by k olors we an nd a triangular fae whose verties are monohromati? Assuming the p olytop e P(k) from Problem 2 exists, the set X from Problem 1 is obtained from P(k) by making a one-point hole in an arbitrary p oint inside every triangular fae. Suh a set X annot b e overed by k onvex sets sine otherwise one of the onvex sets would ontain three verties of a triangular fae. The invisibility graph I(X) an b e olored by 13 olors in the following way. All the verties of P(k) get olor 1 . Taner [7℄ has shown that the edges of every 2 -dimensional simpliial omplex PL-emb eddable in R3 an b e olored by 12 olors so that for every triangular fae, the three edges on its b oundary have three dierent olors. This applies, in partiular, to the 2 -skeleton of every 4 -dimensional onvex simpli- ial p olytop e. We use olors 2,3,...,13 to olor the interiors of edges of P(k) in this way. For eah triangular fae and eah p oint p on its b oundary, the interior of the segment oneting the one-p oint hole with p is olored by the olor of p . All the remaining p oints of X are isolated in I(X) and thus may b e olored arbitrarily. The b oundary omplex of a 4 -dimensional onvex simpliial p olytop e is a sp eial ase of a triangulation of S3 . If we relax the ondition on p olytopality in Problem 2 and ask only for a triangulation of S3 , then the answer is yes. Heise et al. [3℄ onstruted, for every k , a 2 -dimensional simpliial omplex linearly emb edded in R3 suh that in every oloring of its verties with k olors at least one of the triangles is mono hromati. We found the same simpliial omplex indep endently, mo difying Boris Bukh's onstrution, whih was ommuniated to us by Martin Taner. The verties of the omplex are plaed on the moment urve and a suitable nonrossing subset of triangles is hosen for the faes. It remains to extend the embedded omplex to a triangulation of the whole R3 , or S3 [1℄. Referenes [1℄ K. Adiprasito, F. Lutz and J. Moller, unpublished manusript. [2℄ M. Breen and D. C. Kay, General deomp osition theorems for m -onvex sets in the plane, Israel Journal of Mathematis 24 (1976), 217233. [3℄ C. G. Heise, K. Panagiotou, O. Pikhurko and A. Taraz, Coloring d -emb eddable k -uniform hyp ergraphs, arXiv:1209.4879 (2012). [4℄ J. Lawrene and W. Morris, Finite sets as omplements of nite unions of onvex sets, Dis- rete & Computational Geometry 42 (2009), no. 2, 206218. [5℄ J. Matou²ek, Letures on Disrete Geometry, Springer-Verlag, New York (2002). [6℄ J. Matou²ek and P. Valtr, On visibility and overing by onvex sets, Israel Journal of Mathematis 113 (1999), no. 3, 341379. [7℄ M. Taner, unpublished manusript. [8℄ F. Valentine, A three p oint onvexity prop erty, Pai Journal of Mathematis 7 (1957), no. 2, 12271235. 106