Stabbing simplices of point sets with k-flats

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Stabbing simplices of point sets with k-flats Javier Cano∗1, Ferran Hurtado†2, and Jorge Urrutia‡1 1Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico City, Mexico. 2Departament de Matemàtica Aplicada, Universitat Politécnica de Catalunya, Barcelona, Spain. Abstract Let Sbe a set of npoints in Rdin general position. A set Hof k-flats is called an mk-stabber of Sif the relative interior of any m-simplex with vertices in S is intersected by at least one element of H. In this paper we give lower and upper bounds on the size of minimum mk-stabbers of point sets in Rd. We study mainly mk-stabbers in the plane and in R3. Introduction A set {x0, . . . , xk} ∈ Rdof k+1 points is called linearly independent if there is no linear combination λ0x0+ · · · +λkxk=0in which at least one λi6= 0,k≤d. A set of points {x0, . . . , xk} ∈ Rdis called affinely independent if the set {x1−x0, . . . , xk−x0}is linearly independent, k≥1. A set consisting of a single point will also be considered as affinely independent. An affine combination of a set of k+1 affinely independent points in Rdis a linear combination λ0x0+· · ·+λkxk of x0, . . . , xksuch that λ0+· · · +λk= 1. The set of affine combinations of k+ 1 affinely independent points of Rdis called a k-flat. In particular, a (d−1)- flat of Rdwill be called a hyperplane. Following our intuition, a 1-flat is a line, and a 2-flat is a plane. A k-flat is isomorphic to the k-dimensional space Rk. A point set Sin Rdis in general position if any subset of Swith at most d+1 elements is affinely independent. An m-simplex of Rdis the convex hull of a set of m+ 1 affinely independent points in Rd,m≤d. For example, in R2a0-simplex is a point, a 1-simplex is a segment and a 2-simplex is a triangle. Given a k-flat hand an m-simplex Pof Rd, we say that hstabs Pif hintersects the relative interior of P. A set of k-flats His called an mk-stabber of a set of points Sif every m-simplex induced by the elements ∗Email: [email protected]. Research supported by project number 178379 Conacyt, México. †Email: [email protected]. Research partially supported by projects MINECO277 MTM2012-30951, Gen. Cat. DGR2009SGR1040, and ESF EUROCORES programme EuroGIGA, CRP ComPoSe IP04: MICINN Project EUI-EURC- 2011-4306. ‡Email: [email protected]. Research supported by project number 178379 Conacyt, México.. of Sis stabbed by at least one element of H. For example, in the plane a set of points Q(respectively lines) is a 30-stabber (respectively a 31-stabber) of point set Sif any triangle with vertices in Scontains an element of Qin its interior (respectively is intersected by a line in Q). In this paper we study the following problem: Given two integers k < m,k < d, and m≤d+ 1, and a set Sof npoints in Rdin general position, how many kflats are needed to stab all the m-simplices generated by the elements of S? In this paper we focus mainly on stabbing all the r-simplices of point sets on the plane or in R3, and give some results for higher dimensions. The problem of finding sets of points that stab all the triangles of a point set has been studied by Katchalsky and Meir [4], and independently by Czyzowicz, Kranakis, and Urrutia [2]. They prove that for any point set Sin the plane in general position with nelements, such that its convex hull has celements, the set of triangles of Scan be stabbed with exactly 2n−c−2points, and that such a bound is tight, as any triangulation of Shas 2n−c−2triangles. Stabbers for other convex holes, such as quadrilaterals and pentagons, have also been studied [1]. Given a point set Sin Rd, we define fm k(S)as the size of the smallest mk-stabber of S. We define fm k(n) as the largest value that a mk-stabber can have over all the point sets Sof Rdwith nelements. With this terminology, the preceding result in the plane translates to f2 0(S)=2n−c−2. In this paper we show upper and lower bounds for fm k(n), for point sets on the plane and R3that are tight up to a constant. 1 Well-separated sets and generalized ham-sandwich cuts A family of convex sets C0, . . . , Ckof Rd,k≤d, is well separated if for any choice of xi∈Ci, the set of points {x0, . . . , xk}is affinely independent. A family P0, . . . , Pkof finite point sets in Rdis well separated if their convex hulls Conv(P0),...,Conv(Pk)are well separated, k≤d. 91 Stabbing simplices with k-flats Notice that in particular, this implies that for any pair of different indexes i, j ≤k, the convex hulls of Piand Pjdo not intersect. Let P0, . . . , Pkbe a family of pairwise disjoint finite point sets in Rd,k≤d. Given positive integers ai≤ |Pi|, an (a0, . . . , ak)-cut is a hyperplane hfor which h∩Pi6=∅and |h+∩Pi|=ai,0≤i≤d, where h+is the half-space bounded below by h. The following result by Steiger and Zao will be useful to us: Theorem 1 ([8]) Let P0, . . . , Pdbe well-separated point sets in Rdsuch that P0∪ · · · ∪ Pdis in general position, and let a0, . . . , adbe positive integers such that ai≤ |Pi|. Then there is a unique (a0, . . . , ad)-cut of P0, . . . , Pd. Finally, we recall the almost folklore result about ham-sandwich cuts: Theorem 2 (Ham-sandwich theorem, [9]) Every dfinite sets in Rdcan be simultaneously bisected by a hyperplane. A hyperplane hbisects a finite set Pif each of the open half-spaces defined by hcontains at most b|P| 2cpoints of P. Now we have all the tools that we will use to give an algorithm for constructing a worst-case optimal mk-stabber for point sets in the plane and in the 3- dimensional space. 2 Stabbers in the plane We start by studying the following problem: How many lines are necessary to stab the set of line triangles (segments) determined by triples (pairs) of elements of a point set Sin the plane? In our previous terminology, determine lower and upper bounds for f1 1(n)and f2 1(n)for point sets on the plane. We first prove: Theorem 3 For any set Sof npoints in the plane r≤f2 1(S)≤ dn 4e, where ris the smallest number such that n 2≤2+2+3+· · · +r. Our bounds are tight. Proof. The lower bound follows from the fact that r lines, no three of which intersect at a point, divide the plane into 2 + 2 + 3 + · · · +rconvex regions, and if a set of rlines stabs all of the triangles with vertices in S, then Shas at most two elements in each of these regions. We now prove that f2 1(S)≤ dn 4e. To this end, we now show how to obtain a set Hwith dn 4estraight- lines that is a 21-stabber of S. To prove our result, it is sufficient to find a set Hwith dn 4elines such that any cell of the arrangement generated by Hcontains at most two elements of S. First, we put in Hone straight line `that separates Sinto two subsets of size dn 2eand bn 2crespectively. Refer to these sets as S1and S2. Clearly, these sets are well separated, and by Theorem 1 we can find a (2,2)- cut for S1and S2. This cut is a line `1that leaves two elements x1, x2of S1and two elements x0 1, x0 2of S2above it. These points are separated from the remaining points of Sby `and `1, if `1contains some element of S1or S2move it slightly. Thus any triangle containing at least one vertex in {x1, x2, x0 1, x0 2}is intersected by `or `1. We repeat this recursively on S1\{x1, x2}and S2\ {x0 1, x0 2},dn 4e − 2times, obtaining a set of dn 4elines (including `and `1) that is a 21-stabber of S. To show that our bound is tight, let Sbe a set of npoints in the plane in convex position labeled p0, p1, . . . , pn−1in counterclockwise order, with neven. Consider the set of n 2triangles pipi+1pi+2,i even, and i≤n 2for every even value of i. Observe that any two of these triangles intersect at exactly one vertex, for n≥6. We claim that any straight line stabs at most 2 of these triangles. This is true since every such triangle has exactly two edges of the convex hull of Pn; then any straight line stabbing one such triangle stabs at least one edge of the convex hull. Any straight line stabs at most two edges of the convex hull, so then it can stab at most two of such triangles. Thus to stab all of those triangles we need at least one straight line for every two triangles. Observe next that if the elements of Sare in convex position, then to stab the edges of the convex hull of Swe need at last dn 4elines. Thus our upper bound is tight.  The key property of Hin the proof of this result is the fact that any cell of the arrangement induced by Hcontains at most two elements of S. Observe that if instead of finding a (2,2)-cut for S1and S2, we use (m−1, m −1)-cuts, then we obtain a set of lines such that any cell of the arrangement generated by them contains at most m−1elements of S. An misland of Sis a subset S0of Swith exactly melements and such that the convex hull of S0contains no element of S\S0in its convex hull. The next result follows easily from the proof of Theorem 3. Theorem 4 For any set Sof npoints in the plane, dn 2(m−1) elines are always sufficient and sometimes necessary to stab all of the mislands of S. In particular, for m= 2, this proves that f1 1(S)≤ dn 2e; that is, to stab the segments of Swe need at most dn 2elines. It is easy to see that the bound dn 2(m−1) e in Theorem 4 is achieved for point sets in convex position. We close this section by observing that the problem of calculating f1 1(S)is equivalent to calculating the minimum number of lines such that in each face of 92 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 the arrangement defined by these lines, there is at most one element of S. This problem is known as the shattering problem and its decision version is known to be NP-complete [5]. 3 Stabbers in the space We consider now the problem of stabbing the tetrahedra induced by an npoint set Sin R3using sets of planes. Our approach is similar to that of the previous section. For the lower bound we will use the following set of npoints in the plane. Let f:R→R3,f(a) = (a, a2, a3).f(R)is known as the momentum curve in R3. Clearly, any plane in R3intersects f(R)in at most 3points. Let Cn={p0, . . . , pn−1}with pi=f(i). Since any plane intersects f(R)in at most 3points, Cnis in general position. Given any segment pipj, let f([i, j]) be the curve containing the points f(x), with i≤x≤j. We call f([i, j]) the shadow of the segment pipjin the momentum curve. The following observation will be useful. Observation 1 Let pi, pj∈Cn. Then any plane intersecting the relative interior of the segment pipjintersects its shadow. Consider the set {t0, . . . , tbn−1 3c}of tetrahedra, such that the vertex set of tiis {p3i, p3i+1, p3i+2, p3i+3}. Observe that the interiors of these tetrahedra are pairwise disjoint, and that tiand ti+1 share exactly one vertex, namely p3i+3. Observation 2 If a plane intersects the interior of a tetrahedron, then it intersects the relative interior of one of its edges. We define the shadow of tias the shadow of the segment p3ip3i+3 which is in fact the union of the shadows of the edges of ti. Then the relative interiors of the shadows of {t0, . . . , tbn−1 3c}are pairwise disjoint. The next lemma follows now directly from Observations 1 and 2: Lemma 5 If a plane stabs ti, then it intersects the relative interior of its shadow. Since any plane intersects the momentum curve at most three times, it follows that any plane intersects at most three elements of {t0, . . . , tbn−1 3c}. By Observation 1, any plane stabbing timust intersect its shadow; thus any any plane stabs at most three elements of {t0, . . . , tbn−1 3c}. Thus we have: Lemma 6 f3 2(n)≥ dn−1 9e. We will now prove that f3 2(n)≤ dn 9e+ 2. To this end, we are going to give an algorithm that splits any point set Sinto a a family of well-separated families of subsets of S. First find two parallel planes π1and π2such that they split Sinto three subsets S1,S2and S3such that ||Si| − |Sj|| ≤ 1,i6=j≤3. That is, each Sicontains bn 3cor dn 3eelements. We now apply the ham-sandwich theorem in R3 to find a plane π3that simultaneously bisects S1,S2 and S3. Let S+ ibe the subset of Sithat lies above π3and S− ithe one that lies below π3, with i= 1,2,3. This gives us two disjoint well-separated families F= {S+ 1, S− 2, S+ 3}and F0={S− 1, S+ 2, S− 3}. Similarly to the algorithm in the previous section, iteratively find (3,3,3)-cuts for F, removing the nine points above the cut until each set in Fcontains at most three points, and adding the cut planes to the 32-stabber. Then repeat the same process for F0. It is now easy to see that the set of planes we obtain has at most dn 9e+ 2 elements, and that they form a stabber of all the tetrahedra with vertices in S. Thus we have proved: Theorem 7 dn−1 9e ≤ f3 2(n)≤ dn 9e+ 2. Observe that using similar arguments we can prove that f2 2(n)≈n/6(stabbing triangles with planes) and f1 2(n)≈n/3(stabbing segments with planes). 3.1 Stabbing 2-simplices of point sets with lines For the problem of stabbing triangles with lines, it is easy to see that in some instances, we need at least 2n−4 2lines. Indeed, consider any set of points Sin R3with npoints in convex position. Observe that the convex hull of Scontains exactly 2n−4triangles, and that any line intersects the interior of at most two of these triangles. Thus we have proved that in R3, f2 1(n)≥n−2. We now prove that 2n−5lines are always sufficient to stab all of the triangles of S. To prove this, first project the elements of Sinto the real plane, thus obtaining a point set S0in R2. It is known that if the convex hull of S0has celements, it is always possible to find a set of points Qwith at most 2n−c−2 points that stabs all of the triangles of S0; see [2, 4]. Each point q∈Qgenerates a vertical line `qpassing through q. Since each triangle Tof Sprojects to a triangle T0of S0, there is a line `q,q∈Qthat stabs T0and thus T. Since in the worst case, the convex hull of S0has three points, we have proved: Theorem 8 In R3,f2 1(n)≤2n−5. 93 Stabbing simplices with k-flats 3.2 Stabbing the 3-simplices of a point set in R3with points We now turn our attention to the problem of stabbing the set of tetrahedra generated by a point set Sin R3using sets of points. We will assume that no two elements of Slie on a line vertical to the real plane. Consider again the momentum curve f(a) = (a, a2, a3), and the set of points Cn={p0, . . . , pn} as defined above. Let 0≤i, j ≤nsuch that i+ 1 < j. Let Ti,j be the tetrahedra with vertex set {pi, pi+1, pj, pj+1}. It is well known [3] that the set of tetrahedra Ti,j, with iand jas above, have disjoint interiors, and form a tetrahedralization of the convex hull of Cn={p0, . . . , pn}. Since any set of points that stabs the tetrahedra of Scontains at least one point in each of these Ti,j, it follows that f3 0(n+ 1) is at least n−1 2. We now prove an upper bound on f3 0(n+ 1). We proceed as follows: For every two elements xi, xj∈S, place a point pi,j slightly above the midpoint of the line segment joining xito xj. For every xi∈S, place a point pislightly below xi. We now prove that the set of points containing all the p0 i,jsand the pi’s stabs all the tetrahedra of S. Consider any four points xi, xj, xk, x`of S. Let H be the convex hull of {xi, xj, xk, x`}. Two cases arise. In the first case, Hprojects to a convex quadrilateral in the plane. In this case, one edge of the convex hull of {xi, xj, xk, x`}is not visible from below. Suppose w.l.o.g. that it is the edge joining xkto x`. Then the point pi,j stabs H. Suppose then that Hprojects to a triangle Ton the plane. Then one vertex of H, say xi, belongs to the interior of T. Two sub-cases arise. In the first sub-case, when we see Hfrom below, xiis not visible. In this case, the point pistabs the convex hull of {xi, xj, xk, x`}. In the remaining sub-case, pi,j stabs H. Thus we have that we can always choose n+1 2+n points that stab the tetrahedra of S. It is not hard to see that we can reduce the above number by 9by observing that if the line segment joining xito xjis not visible from below, and this line segment belongs to the convex hull of S; then the point pi,j is redundant. Also if a point xibelongs to the convex hull of Sand is visible from below, then piis redundant. Thus we have proved: Theorem 9 n−1 2≤f3 0(n+ 1) ≤n+1 2+n−9. 4 Some thoughts on higher dimensions Some of the results in this paper; e.g. Lemma 5 and Lemma 6, generalise easily to higher dimensions, yielding the following result: Lemma 10 In Rd,dn−1 d2e ≤ fd d−1(n). And in general: Lemma 11 In Rd,dn−1 dm e ≤ fm d−1(n). To finish this paper, we conjecture: Conjecture 1 fd m(n)≈n m·d. References [1] J. Cano, A. García, F. Hurtado, T. Sakai, J. Tejel, J. Urrutia, Blocking the k-holes of point sets in the plane, submitted. [2] J. Czyzowicz, E. Kranakis, J. Urrutia, Guarding the convex subsets of a point set, in: 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, Canada, 2000, 47–50. [3] B. Grünbaum, Convex Polytopes, Interscience Monographs in Pure and Applied Mathematics, Vol. XVI, John Wiley & Sons, London-New York-Sydney. [4] M. Katchalski, A. Meir, On empty triangles determined by points in the plane, Acta Math. Hungar 51 (1988), 323–328. [5] R. Freimer, J. S. B. Mitchell, C. D. Piatko, On the Complexity of Shattering Using Arrangements, in: Proceedings of the 2nd Canadian Conference on Computational Geometry, 1990, 218–222. [6] A. Pór, D. R. Wood, On visibility and blockers, J. Computational Geometry 1(1) (2010), 29–40. [7] T. Sakai, J. Urrutia, Covering the convex quadrilaterals of point sets, Graphs and Combinatorics 38 (2007), 343–358. [8] W. Steiger, J. Zhao, Generalized Ham-Sandwich Cuts, Discrete and Computational Geometry 44(3) (2010), 535–545. [9] H. Steinhaus, A note on the ham sandwich theorem, Mathesis Polska 9(1938), 26–28. 94