Clique-Width of Point Configurations* Onur Cagmci1 I0000-0002-4785-7496] petr Hliněný1 I0000-0003-2125-1514] Filip Pokrývka1, and Abhisekh Sankaran2 1 Faculty of Informatics, Masaryk University, Brno, Czech Republic onur@mail.muni.cz hlineny@fi.muni.cz xpokryvk@fi.muni.cz 2 Department of Computer Science and Technology, University of Cambridge, UK abhisekh.sankaran@cl.cam.ac.uk Abstract. While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of clique-width to geometric point configurations represented by their order type. We study basic properties of this clique-width notion, and relate it to the monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given. Keywords: point configuration • order type • fixed-parameter tractabil-ity • relational structure • clique-width 1 Introduction An order type is a useful means to characterize the combinatorial properties of a finite point configuration in the plane. As introduced in Goodman and Pollack [18,19], the order typeoi a given set P of points assigns, to each ordered triple (a, b, c) € Pa of points, the orientation (either clockwise or counter-clockwise) of the triangle abc in the plane. More generally, if the point set P is not in a general position, the triple (a, b, c) may also be collinear (as the natural third option). Knowing the order type of a point set P is sufficient to determine some useful combinatorial properties of the geometric set P, such as the convex hull of P and other. For example, problems of finding convex holes in P or dealing with the intersection pattern of straight line segments with ends in P, can be solved by looking only at the order type of P and not on its geometric properties. That is why order types of points sets are commonly studied from various perspectives in the field of computational geometry, e.g., [20,2,4,6,17,28,5,3]. On the other hand, knowing the order type of P is obviously not sufficient to answer questions involving truly "geometric" aspects of P, e.g., distances in P * O. Cagirici, P. Hliněný and F. Pokrývka have been supported by the Czech Science Foundation, project no. 20-04567S. A. Sankaran has been supported by the Leverhulme Trust through a Research Project Grant on 'Logical Fractals'. 2 O. Qagirici, P. Hliněný F. Pokrývka and A. Sankaran (straight-line or geodesic), or angles between the lines or the area of polygons within P. Nevertheless, even in such geometry-based problems, a more efficient subroutine computing with the order type of P might speed-up the overall computation, which can be a promising direction for future research. Unlike in the area of graphs and graph algorithms, where structural width parameters are very common for many years, at least since the 90's, no similar effort can be seen in combinatorial and computational geometry. We would like to introduce, in this paper, possible combinatorial handling of "structural complexity" of a given point configuration P through defining its "width" (which we would assume to be small for the studied inputs). Note that, although the desired width would be a concrete natural number, we will not be interested in the exact value of it, but instead study whether the width would be bounded or unbounded on a given class of point configurations. Inspired by graph structure parameters, the obvious first attempt could be to extend the traditional notion of tree-width [27]. Such an extension is technically possible (cf. tree-width of the Gaifman graph of a relational structure), but the huge problem is that for the tree-width to be upper-bounded, the underlying structure must be "sparse" - in particular, it can only have a linear number of edges / tuples. This is clearly not satisfied for the order type in which about half of all triples are of each orientation. A better option comes with another traditional, but not so well-known, notion of clique-width [13]. Clique-width can be bounded even on dense graphs, such as on cliques, and, similarly to the case of Courcelle's theorem [10] for tree-width, clique-width also enjoys some nice metaalgorithmic properties, e.g. [12,16]. This includes solving any decision (and some optimization as well) problems formulated in the monadic second-order (MSO) logic in linear time. Hence, alongside with the (Section 2) proposed definition of the clique-width of point configurations, we will introduce the MSO language of their order types and discuss which problems can be formulated in this language (and hence solved in linear time if a point set with a decomposition of bounded clique-width is given on the input). Paper organization. We introduce order types of point configurations, viewed as ternary relational structures, in Section 2. Then we formally define their clique-width as that of relational structures. We also show why a technically simpler-looking "unary" clique-width (which is closer to the traditional graph clique-width) does not work well for order types. In Section 3 we speak about MSO logic of order types, and give a basic overview of its use and expressive power. We restate classical logic results on clique-width characterization and metaalgorithmics (Theorems 5 and 7). We continue the study in Section 4 with a few concrete interesting examples of bounding the clique-width of special point sets (Theorem 8), and of solving some geometric point problems, which are otherwise NP-hard, for inputs of bounded clique-width (Theorems 9, 10 and 11). We conclude with some questions and suggestions in Section 5. Due to space restrictions, details of the (*)-marked statements are left for the Appendix. Clique-Width of Point Configurations 3 2 Order Types and Clique-Width We now recall the notion of an order type in a formal setting, and propose a definition of the clique-width of (the order type of) a point configuration, based on a natural specialization of the very general concept of clique-width of relational structures. A relational structure S = (U, Rf,..., Rf) of the signature a = {R\,..., Ra} consists of a universe (a finite set) U and a (finite) list of relations Rf,..., Rf over U. For instance, for graphs, U = V(G) is the vertex set and Rf = E(G) is the binary symmetric relation of edges of G. For a set of points P, here always considered in the plane, consider a map uj : Pa —> {+, —, 0} where uj(a, b, c) = 0 if the triple of points3 a, b, c is collinear, ,Pj). Proof outline. Let the points of P be p\, p2,..., pn in the counter-clockwise order (starting arbitrarily). We start with pi and stepwise add p2, pz etc., changing previous points to label 1 and the added point created with unique label 2. See Figure 1. Along the steps, right after the creation of pj, we add the binary label 3 to all pairs labelled 1 and 2, i.e., to (pi,pj) for all i < j, and create the order triple (pi,Pi',Pj) over all pairs (pi,Pi>) of label 3, i, i' ^ j and pj of label 2. This construction witnesses that the clique-width of P is at most 4. On the other hand, take unary clique-width with £ labels, and \P\ > 2£ + I. An arbitrary ^-expression for fi{P) must have a union operation (the "last" one) over two subsets such that one has more than £ points, and so two points a, b of the same label by the pigeon-hole principle. Let c be any point from the other set. Then there is no way, based on the labels, to distinguish between the triples (a, b, c) and (b, a, c), which must have the opposite orientations in £2(P). Therefore, the clique-with of P must be at least £+1. Annotated point configurations. In some situations, it may be useful to consider a point configuration P with additional information (or structure) on the points or selected pairs of them. An exemplary use case for such annotations is to study polygons, with P as the vertex set, for which case we are considering an order type fi{P) together with a directed Hamiltonian cycle on P representing the counter-clockwise boundary of P. Formally, we simply consider relational structures (over P) with the signature consisting of the ternary order type and arbitrary binary or unary symbols. The clique-width of such an annotated point configuration P is, naturaly, as in Definition 1 with additional rules that some of the auxiliary unary and binary labels are at the end turned into the desired unary and binary relations on P. 3 MSO logic of order types The beginning of this section is devoted to a short introduction of the monadic second-order (MSO) logic of relational structures. Recall a relational structure S = (U, Rf,..., Rg) of the signature a = ..., Rq}. 6 O. Qagirici, P. Hliněný F. Pokrývka and A. Sankaran The language of MSO logic (of the signature a) then consists of the standard propositional logic, quantifiers V, 3 ranging over elements and subsets of the universe U, and the relational symbols R\,..., Rq with the following meaning: for Ri of arity a, we have S |= Ri(xi,..., xa) if and only if (x\,..., xa) € Rf. In our specific case of order types fi{P) of point sets P, we use the relational symbol or dec w( x i, x 2, £3) for £2 within MSO logic. For example, we can express that a point y lies strictly in the convex hull of points xi,X2,x% as follows ordccw(xi, X2, X3) A /\ ^ ^ ^ ordccw(xi,xi+i,y)^ V (1) V \ordccw{x-i,,X2,xi) A f\ ^ ^ ^ ordccw(xi+i, Xi, , where indices are taken modulo 3. More generally, we can express that a point y € P belongs to the convex hull (not necessarily strictly now) of a set X C P, y ^ X, with the following formula: convhull(X, y) = \/x € X 3x' € X [x ^ x' A (2) \/z{{z = jV(z6lAz/i, x')) —> -1 ordccw(x', x, z))] Then we may express, for example, that a set X C P is a convex hole (i.e., no point outside of X belongs to the convex hull of X, and no point of X belongs to the convex hull of the rest of X) with the following: Vy^X (-. convhull(X, y)) A VFCXVz€X(convhull(Y, z) z € Y) (3) Further similar examples are easy to come with. Interpretations and transductions. We sketch the concept of "translating" between relational structures. Consider relational signatures a = {R\,..., Rq} and r = {R'i,..., R't}. A (simple) MSO interpretation of r-structures in a-structures is a t-tuple of MSO formulas W = (ipi : 1 < i < t) of the signature a, where the number of free variables of ipi equals the arity at of R[. A r-structure T is interpreted in a cr-structure S via W if T and S share the same ground set U and, for each 1 < i < t, we have (x\,... ,xai) G R'{T ^=p- S \= ipi(x\,... ,xai). As a short example, consider a point set P and its mirror image P'. Then the order type fi(P') can be interpreted in fi{P) simply by taking ipi(a, b, c) = ordccw(b, a, c). The true power of interpretations will show up in the following. There is a more general concept of a transduction from a cr-structure S to a set of r-structures which, before taking an (MSO) interpretation, has abilities (in this order of application); (i) to equip S with a fixed number of arbitrary parameters given as unary labels (because of this, the result of a transduction is not deterministic, but a set of r-structures), (ii) to "amplify" the ground set of S by taking a bounded number of disjoint copies of S, and (iii) to subsequently restrict the ground set by a unary MSO formula. See the Appendix and/or Courcelle and Engelfriet [11] for more technical details on transductions. For a class of relational structures S, the image in a transduction W of the class S is the union of all transduction results, precisely, 9 TTí":*;'"' """V-íl * "■■'•'■«f P3fe+1 Fig. 2. Illustrations of the two parts of Theorem 8. (a) Labelling for an expression of bounded width, (b) A sketch of interpreting a large grid within the point configuration. Proof outline. In case (a), we first create the d points of P \ Pq, each with its unique label, and their counter-clockwise order triples. See Figure 8(a). Then we stepwise create the collinear points of Pq, ordered from left to right. During the steps, we add binary labels on Pq between each pair from left to right, and we also in the right order create the needed order triples having one point in Pq and two points in P \ Pq. At the end, we easily create from the binary labels on Pq the remaining order triples having two points in Pq and one in P\ Pq. In case (b), if d = 1, we construct an expression simlarly as in Proposition 4, but we simultaneously proceed in two subsequences of the counter-clockwise perimeter of Pq, "opposite" to each other. This process allows us to create also the order triples involving the sole point of P \ Pq (in "the middle"). In case (b) with d > 2, we present a construction informally shown in Figure 8(b). The underlying idea is to construct collinear triples "through" the points of P\Pq, such as the depicted triples po, m, qo and qo, n,pk- Since collinear triples are easy to detect within the order type, we can this way interpret the binary relation between po and pk, and analogously between subsequent p\ and Pk+i and so on (see the green dashed arrows in the picture). We can also routinely describe in MSO logic the neighbouring pairs of vertices of a convex hull, see x and x' in (2). Consequently, in such a suitably constructed set P, we can interpret an arbitrarily large square grid graph on the points po,pi,... ,pk,Pk+i, Since the squre grid is a folklore basic example of unbounded clique-width [11], we get from Corollary 6 that the clique-width of such configurations P (with d = 2) is unbounded. Some NP-hard problems of point configurations As already mentioned, perhaps the most interesting computing application of clique-width of point sets could be in designing algorithms which run in parameterized polynomial, or even linear, time with respect to the clique-width as the parameter. This is especially relevant for problems for which no such algorithms are believed to exist in general, such as for NP-hard problems. A parameterized problem has an FPT algorithm if the algorithm runs in time 0(f(d) ■ nc) where / is an arbitrary computable function of the (fixed) parameter d, and c is a constant. If c = 1, then we speak about a linear FPT algorithm (e.g., this is the complete case of Theorem 7). Clique-Width of Point Configurations 9 Since, except graph clique-width, there is no known FPT algorithm (even approximation one) for finding a clique-width expression of relational structures of bounded clique-width, we always must assume that an expression of bounded width is given alongside with the input point configuration. Notice that for the above presented examples of small clique-width, the relevant expressions are very natural and easy to come with. Recall also related Remark 2. General position subset. This problem asks whether, for a given point set P and integer k, there exists a subset Q C P such that no three points of Q are collinear and \Q\ > k. This problem is NP-hard and APX-hard by [15]. Theorem 9. Assume a point set P is given alongside with a clique-width expression (for H(P)) of width d. Then the General position subset problem of P is solvable in linear FPT time with respect to the parameter d. Proof. We write the MSO formula ip(X) = Va;, y,z £X[x^y^z^x^ ( ordccw(x, y, z) V ordccw(y, x, z))] to say that no three points in X are collinear, and then compute using Theorem 7 the value vnax-n(p)\=ip(x) \X\ and compare to k. □ A very similar simple approach works also for the NP-hard problem Hitting set for induced lines [26], which asks for a minmum-cardinality subset H c P such that the lines between each pair of points of P all contain a point of H. Minimum convex partition. Consider a given point set P and an integer k. The objective of this problem [14] is to decide whether the convex hull conv(P) of P can be partitioned into < k convex faces. By a convex face in this situation we mean the convex hull of a subset Q C P which is a convex hole of P (recall (3)). Note that in our definition Q must be strictly convex, but we may as well consider the non-strict variant in which points of Q are allowed to lie on the boundary of conv(Q) not in the vertices (and the arguments would be similar). This problem has been recently claimed NP-hard [21]. Unfortunately, inherent limitations of MSO logic do not allow us to directly formulate the minimum convex partition as an MSO optimization problem (one is not allowed to quantify set families), but we can handle it if we take k as an additional parameter. Theorem 10. (*) Assume a point set P given alongside with a clique-width expression of width d. The minimum convex partition problem of P into < k convex faces is solvable in linear FPT time with respect to the parameter d + k. Proof outline. Let convhole(X) denote the MSO formula (3). We may now write where the subformula convpartition checks whether the convex hulls of the sets Xi partition conv(P). At this point, we know that each X{ is a convex hole in P, and we further test for set inclusion and the following two conditions: — the boundaries of conv(Xi) and conv(Xj) (1 < i < j < k) do not cross, and — every boundary edge of conv(Xi) is, at the same time, a boundary edge of exactly one of conv(Xj) (i ^ j) or of conv(P). Both conditions can be, although not easily, stated in MSO over order types. 10 O. Cagirici, P. Hliněný F. Pokrývka and A. Sankaran Fig. 3. Guarding a terrain: the two black square vertices guard the whole terrain, but the bottom horizontal segment is not seen by any single one of them. To turn this (pair of guards) into a valid segmented terrain guarding solution, we may add the hollow point as an additional vertex of the terrain. Terrain guarding. Another NP-hard problem formulated on point sets [23] is that of guarding an a;-monotone polygonal line L with the given vertex set P. The objective of guarding is to find a minimum-cardinality vertex guard set G C P such that every point £ on L is seen by some point g € G "from above the terrain", that is, the straight line segment from g to £ is never strictly below L. Note that the point set P (no two points of the same ^-coordinate) uniquely determines the terrain L, with the vertices ordered by their ^-coordinates as P = (pi,p2, ■ ■ ■ ,Pn)- However, the order type fi{P) does not (unless we would add an auxiliary point "at infinity" in the y-axis direction). That is why we assume the terrain L given as a relational structure consisting of ternary fi{P) and the binary successor relation consisting of the pairs (pi,pi+i) for 1 < i < n. There is one further complication in regard of the order type fi{P) of the terrain in this problem: if, in an instance, some edge of L is seen together by two guards, but no one sees the full edge, then knowing only fi{P) is not sufficient to verify validity of such a solution (see Figure 3). That is why we define here the Segmented terrain guarding variant in which every segment of L must be seen by a single vertex guard g and, moreover, there is a dedicated subset Pi C P such that the guards are selected from g € P\. By a natural subdivision of terrains in the hard instances of terrain guarding [23] we immediately get that also Segmented terrain guarding is NP-hard. Theorem 11. (*) Assume a polygonal terrain L given alongside with a clique-width expression of width d (defining both the successor relation and the order type of the vertices, cf. end of Section 2). The Segmented terrain guarding problem of L is solvable in linear FPT time with respect to the parameter d. Proof outline. We show a formula seguard(X) stating that every segment of the terrain L is seen by one point of X. There we verify that, for every successive pair of vertices (pi,pi+i) of L, there exists x € X such that; — the triple (x,pi,pi+i) is oriented counter-clockwise (for x to see the segment PiPi+i "from above"), and — no "peak" z on L between pi,pi+i and x is oriented clockwise from (x,pi+i) (if z is to the left of x) or counter-clockwise from (x,pi) (z to the right of x). This suffices since L is a;-monotone. Then Theorem 7 finishes the argument. We can similarly handle the orthogonal terrain guarding problem which is also NP-hard [9]. Another possible extension is to minimize the sum of weighted Clique-Width of Point Configurations 11 guards, using a weighted variant of Theorem 7 (as in [12]). However, our approach to terrain guarding cannot be directly extended to the traditional and more general Art gallery (guarding) problem [24], not even in the adjusted case when each edge of the polygon is seen by a single vertex guard. This is due to possible presence of "blind spots" in the interior of the polygon which cannot be determined knowing just the order type fi{P) and the boundary edges of the polygon on P. Interested readers may find more in the Appendix. Polygon visibility graph. As we have mentioned the Art gallery problem, we briefly add that poeple are also studying problems related to the visibility graph of a given polygon Q. The visibility graph of Q has the same vertex set as Q and the edges are those line segments with ends in the vertices of Q which are disjoint from the complement of the polygon. We give the following toolbox: Theorem 12. (*) Assume a polygon Q with vertex set P given as a relational structure consisting of the order type fi{P) and the counter-clockwise Hamil-tonian cycle of the edges of Q. Then the visibility graph of Q has an MSO interpretation in Q. 5 Conclusions We managed to show, in this limited space, only few example applications of bounding the clique-width in efficient parameterized algorithms for geometric point problems. More examples of similar kind could be added but, as a future work, we would especially like to investigate possible applications to "metric" problems. Of course, MSO logic of order types cannot express metric properties of a point set, but it could be possible that in some problems the enumerative part of Theorem 7 provided us with a relatively short list of small subconfigu-rations which would then be processed even by brute force, resulting in a faster algorithm. For instance, we suggest to investigate in this manner the problem of a minimum area triangle on a given point set, which is in general 3SUM-hard (that is, not believed to have a subquadratic algorithm). Another possible extension would be to consider order types in dimension 3 (or higher), but then even a strictly convex point set could easily have unbounded clique-width - the quaternary relational structures of such order types just seem to be too complex even in very simple cases. Lastly, we mention another very natural question; can the clique-width of a point configuration be at least approximated by an FPT algorithm with the width as the fixed parameter? Such an approximation is possible in the case of graph clique-width [25,22], thanks to the close relation of graph clique-width to rank-width and to binary matroids. Perhaps the natural correspondence of order types to oriented matroids could be of some help in this research direction. Acknowledgments. We would like to thank to Achim Blumensath and Bruno Courcelle for discussions about the clique-width of relational structures. 12 O. Qagirici, P. Hliněný F. Pokrývka and A. Sankaran References 1. Adler, H., Adler, I.: A note on clique-width and tree-width for structures. CoRR abs/0806.0103 (2008), http://arxiv.org/abs/0806.0103 2. Aichholzer, O., Aurenhammer, F., Krasser, H.: Enumerating order types for small point sets with applications. Order 19(3), 265-281 (2002) 3. Aichholzer, O., Balko, M., Hoffmann, M., Kyncl, J., Mulzer, W., Parada, L, Pilz, A., Scheucher, M., Valtr, P., Vogtenhuber, B., Welzl, E.: Minimal representations of order types by geometric graphs. In: GD. Lecture Notes in Computer Science, vol. 11904, pp. 101-113. Springer (2019) 4. Aichholzer, O., Krasser, H.: Abstract order type extension and new results on the rectilinear crossing number. Comput. Geom. 36(1), 2-15 (2007) 5. Aichholzer, O., Küsters, V., Mulzer, W., Pilz, A., Wettstein, M.: An optimal algorithm for reconstructing point set order types from radial orderings. Int. J. Comput. Geometry Appl. 27(1-2), 57-84 (2017) 6. Aloupis, G., Iacono, J., Langerman, S., Ozkan, O., Wuhrer, S.: The complexity of order type isomorphism. In: SODA. pp. 405-415. SIAM (2014) 7. Blumensath, A.: A model-theoretic characterisation of clique width. Ann. Pure Appl. Logic 142(1-3), 321-350 (2006) 8. Blumensath, A., Courcelle, B.: Recognizability, hypergraph operations, and logical types. Inf. Comput. 204(6), 853-919 (2006) 9. Bonnet, E., Giannopoulos, P.: Orthogonal terrain guarding is NP-complete. JoCG 10(2), 21-44 (2019) 10. Courcelle, B.: The monadic second order logic of graphs I: Recognizable sets of finite graphs. Inform, and Comput. 85, 12-75 (1990) 11. Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: a Language-Theoretic Approach, Encyclopedia of Mathematics and Its Applications, vol. 138. Cambridge University Press (2012) 12. Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125-150 (2000) 13. Courcelle, B., Engelfriet, J., Rozenberg, G.: Graph Grammars and Their Application to Computer Science: 4th International Workshop Bremen, Germany, March 5-9, 1990 Proceedings, chap. Context-free handle-rewriting hypergraph grammars, pp. 253-268. Springer Berlin Heidelberg (1991) 14. Demaine, E., Fekete, S., Keldenich, P., Krupke, D., Mitchell, J.: Geometric optimization challenge, part of CG Week in Zurich, Switzerland, June 22-26, 2020, https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2020/ 15. Froese, V., Kanj, I.A., Nichterlein, A., Niedermeier, R.: Finding points in general position. Int. J. Comput. Geometry Appl. 27(4), 277-296 (2017) 16. Ganian, R., Hliněný, P.: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discrete Applied Mathematics 158(7), 851-867 (2010) 17. Goaoc, X., Hubard, A., de Joannis de Verclos, R., Sereni, J., Volec, J.: Limits of order types. In: Symposium on Computational Geometry. LIPIcs, vol. 34, pp. 300-314. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015) 18. Goodman, J.E., Pollack, R.: Multidimensional sorting. SIAM J. Comput. 12(3), 484-507 (1983) 19. Goodman, J.E., Pollack, R.: Upper bounds for configurations and polytopes in rd. Discrete fe Computational Geometry 1, 219-227 (1986) Clique-Width of Point Configurations 13 20. Goodman, J.E., Pollack, R., Sturmfels, B.: Coordinate representation of order types requires exponential storage. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 405-410. ACM (1989) 21. Grelier, N.: Minimum convex partition of point sets is NP-hard. CoRR abs/1911.07697 (2019), http://arxiv.org/abs/1911.07697 22. Hliněný, P., Oum, S.: Finding branch-decomposition and rank-decomposition. SIAM J. Comput. 38, 1012-1032 (2008) 23. King, J., Krohn, E.: Terrain guarding is NP-hard. SIAM J. Comput. 40(5), 1316-1339 (2011) 24. Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Information Theory 32(2), 276-282 (1986) 25. Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Corn-bin. Theory Ser. B 96(4), 514-528 (2006) 26. Rajgopal, N., Ashok, P., Govindarajan, S., Khopkar, A., Misra, N.: Hitting and piercing rectangles induced by a point set. In: COCOON. Lecture Notes in Computer Science, vol. 7936, pp. 221-232. Springer (2013) 27. Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309-322 (1986) 28. Roy, B.: Point visibility graph recognition is NP-hard. Int. J. Comput. Geometry Appl. 26(1), 1-32 (2016) 14 O. Cagirici, P. Hliněný F. Pokrývka and A. Sankaran Appendix A Supplements for Section 2 Proposition 13 (4). Let P be an arbitrary finite set of points in a strictly convex position. Then the clique-width of P is bounded by a constant, while the unary clique-width of P is unbounded. Proof. We show that cw(P) = 4 by constructing an expression £ for Q = fž(P) using unary labels 1 and 2 and a binary label 3. Let the points of P be enumerated as pi,p2, ■ ■ ■ ,Pn in the counter-clockwise order (the starting point does not matter). We create a starting point pi of label 1, and for k = 2, 3,..., n = \P\ we iterate this sequence of operations in our expression £: — (wl) create a new point pk of label 2, and (w2) make the union of previous {pi,... ,pk-i} with {pk}', — (w3) for all points a, c such that a is of label 1 and c of label 2, give the pair (a, c) label 3; — (w4) for all distinct points a, b, c such that c is of label 2 and (a, b) is of label 3, add to Í2 the cyclic closure of (a, b, c); — (w5) relabel all points of label 2 to label 1. Notice that during every iteration, the only point c of the label 2 is c = pk, and after iteration number k, the binary label 3 is given exactly to pairs (pi,pj) such that 1 < i < j < k. Hence the operation (w4) adds triples (pi,Pj,Pk) and their cyclic closure, exactly when 1 < i < j < k, which all indeed belong to Í2(P). On the other hand, in every counter-clockwise triple (pi,Pj,Pk) of P we may assume k is the largest index, and then i < j < k by our indexing of P. So the pair (pi,pj) gets label 3 in above iteration number j, and then the triple (pi,Pj,Pk) is added to Í2 in iteration number k. Therefore, the value Í2 of £ satisfies Í2 = Í2(P). Next, in order to prove that the unary clique-width of P is unbounded, we show that every expression for fž(P) which uses only unary labels - see (u3') - must use at least \n/2~\ labels where n = \P\. For a contradiction, let £ be an expression with I unary labels whose value is fž(P), and assume n > 21+1. Imagine the last application of the union operation (u2), which makes the union of the values of subexpressions £\ and £2. Since £\ and £2 together make all n points of P, one of them, say £\, makes at least I + 1 of the points. By the pigeon-hole principle, some two distinct points a, b created in £\ end up with the same label in the value of £\. (We remark that a and b may be created with different labels, and possibly relabelled several times, but we speak about the final label they get within £\.) Let c be any point created by £2- Among the two triples (a, b, c) and (&, a, c), exactly one is counter-clockwise in P, say (a, b, c). The triple (a, b, c) can be created only after the union of £\ and £2 ■ However, whenever an application of the operation (u3') creates the triple (a, b, c), since the labels of a and b are already the same and must stay the same, this application adds also the triple (&, a, c), which is in a contradiction to fž(P) being the value of £. □ Clique-Width of Point Configurations 15 B Supplements for Section 3 The concept of transductions. We provide formal details on the concept of an MSO transduction, which were skipped for simplicity in the main paper. Consider relational signatures a = {R\,..., Rq} and r = {R[,..., R't}. Recall that a (simple) MSO interpretation of r-structures in cr-structures is a t-tuple of MSO formulas W = (ipi : 1 < i < t) of the signature a, where the number of free variables of ipi equals the arity at of R[. A basic MSO transduction <5o of a relational cr-structure S is a (t + 2)-tuple (x,^,ipi,---,ipt) of MSO formulas of the signature a, where \ is miliary, v is unary and ipi are as in an MSO interpretation above. The outcome of 5q{S) is undefined (empty) if S ^= Xj and otherwise, <5o maps the structure S on the ground set U into a single r-structure T on the ground set [/' = {«€ U \ S \= v(v)}- The relational symbols of r are interpreted on U' as follows; for each 1 < i < t, we have (x\,..., xai) € R'{T <^^> S |= ipi(xi,..., xai). The m-copy operation maps a structure S on the ground set U to the relational structure Sm on the ground set Um = U x {l,...,m}, such that the subset U x {i} for each i = 1,2 ..., m induces a copy of the structure S (there are no tuples between distinct copies). Additionally, Sm is equipped with a binary relation ~ and unary relations Qi,..., Qm such that; (u, i) ~ (v, j) for u,v € U iff u = v, and Qi = {(v, i) : v € U}. The p-parameter expansion maps a structure S to the set of all structures which result by an expansion of U by p unary predicates (as arbitrary labels). Altogether, a many-valued map r is an MSO transduction if it is 5 = 5q ojoe where 5q is a basic MSO transduction, 7 is a m-copy operation for some m, and e is a p-parameter expansion for some p. We remark, once again, that the result of a transduction 5 of one structure is generally a set of structures, due to the involved p-parameter expansion. For a class C of structures, the result of a transduction 5 of the class C is the union of the particular transduction results, precisely, 5(C) := Usee ^(^)- Theorem 5 and Definition 1. We also add more details about the characterization of clique-width in Theorem 5 and the related aspects of Definition 1. Blumensath and Courcelle in [8, Proposition 27] claim, in particular, logical equivalence of the following two properties of a class C of relational structures: — [8, Proposition 27 (iii)], C is the image of an MSO transduction of a regular subclass of the class of finite trees (implicitly directed and labelled), — [8, Proposition 27(h)], C is the set of values of expressions consisting of the disjoint union and of all quantifier-free operations over a fixed reference signature (wrt. C). The reference signature in the latter point is actually a set of multi-ary labels used in the expressions whose values form C (hence the direct correspondence with expressions and their width in Definition 1). To be formally precise with Theorem 5 and our Corollary 6, we hence need to formulate the following claim relating the latter point back to our Definition 1: 16 O. Qagirici, P. Hliněný F. Pokrývka and A. Sankaran Lemma 14. A class S (of signature a) of order types of point configurations is of bounded clique-width, if and only if there exists a reference signature r D a, such thatS is the set of values (restricted to signature a) of expressions consisting of the disjoint union and of all quantifier-free operations over r. Proof. The forward implication is trivial since the operations in Definition 1 are quantifier-free. For the backward implication, the following is a key idea: since only quantifier-free operations are used, the decision on an order-type triple of a member R € S, say triple (a, b, c), depends only on the labels induced on the subset {a, b, c} of the ground set of R. This finding inductively extends to all operations in the respective expression £ valued R, which lead to a decision on the triple (a, b, c). We hence focus on a "subexpression" £q of £ which consists only of the operations having domain in {a, b, c}. Consider the last disjoint union operation in £q which, up to symmetry, made a disjoint union of substructures on {a, b} and {c}. The final decision on (a, b, c) depends only on the labels on {a, b} and on {c} just before the union operation (further relabellings cannot bring new piece of information). Hence we can encode the information leading to a decision on (a, b, c) in a unary label on c and a binary label on (a, b) (or symmetrically on (b, a)). Recursively, we argue that binary labels on (a, b) depend only on the unary labels of a and b. Therefore, operations as in Definition 1 are sufficient to construct the considered order-type structure R under suitable signature. □ C Supplements for Section 4 Theorem 15 (8). Let P be a point configuration, P0 c P and d = \P\ Pq\. a) If all points of Pq are collinear, then the clique-width of P is in O(d). b) Assume the points of Pq are in a strictly convex position. If d < I, then the clique-width of P is bounded (by a constant). On the other hand, there exist examples already with d = 2 and unbounded clique-width of P. Proof, (a) We show that cw(P) = d + 8 by constructing an expression £a for fia = fi{P) using d + 2 unary labels and three binary labels. See Figure 8(a). We choose a direction of the line £0 through P0 and enumerate the points of P0 in the direction of £q as p\,p2, ■ ■ ■ ,Pn, and the points of P \ Pq as qi,..., qri- As for the expression £a, we first create independently all points qi,..., qri, each with its own unique label. Then we use auxiliary two binary labels to add the needed order triples for them, based on the unique unary labels. In the second stage, we create the points p\,p2, ■ ■ ■ ,Pn, one by one, at step i assuming that pi,... ,Pi-i are labelled 1 and new pt gets label 2. At this step we give binary label 3 to all pairs which are of labels 1 and 2 in this order (that is, to the pairs (pj,pi) for all j < i), and we also add to £2a all needed order triples involving pt and two points of P \ Pq (since we again have unique labels for such triples). Clique-Width of Point Configurations 17 In the third final stage, we add the order triples (qk,Pj,Pi), such that (j)j,Pi) is of the binary label 3 and (which still holds its unique label) is in the counterclockwise orientation from the line £q. We analogously add the triples (qk,Pi,Pj) if qk is clockwise from £q. (b) Case of d = 1. We enumerate the points of P0 in the clockwise orientation as pi,p2, ■ ■ ■ ,Pn- Let P\Pq = {to}. Let k be the least index such that (pi,m,pk) is counter-clockwise. We denote by qi = Pi, qri = Pi+i, ■■■ We now use the same construction of an expression as in the proof of Proposition 4, but now simultaneously applied to p\,p2, ■ ■ ■ and to qi, c/2, • • • such that we always process together pt and qj of the least index such that (pi, to, qj) stays counter-clockwise. This results in an expression of width 8 which correctly adds also the order triples involving the "middle" point to. (b) Case of d = 2. We give a construction, sketched in Figure 8(b), of such an order type of unbounded clique-width. Consider the points of P\Pq = {to, n} and the points of Pq named in the counter-clockwise direction po,pi,..., qo, q\,... We choose an arbitrary k and place the points of Pq on the convex hull such that we have collinear triples {pi, to, qi) and {pi+k, n, qi) for i = 0,1, 2,..., k2 — 1. No other triples in the construction are collinear. Within the order type fi{P), we can uniquely identify with MSO the points to, n - as those two belonging to the convex hull of the remaining points. We can then write formulas collin(x,y, z) = -> ordccw(x,y, z) A ->ordccw(y,x, z), and jk(%,y) = 3z coUin(x,m, z) A collin(y,n, z). Then 7^ relates pt to pj (i.e., fi{P) |= Jk(Pi,Pj) V Jk(Pj,Pi)) if and only if j = i + k or vice versa. We can also in MSO describe the successor relation on the boundary of the convex hull of Pq, that is the pairs (pi,pi+i), cf. (2). In this way we get an MSO interpretation of the k x k square grid graph in £2(P). Consequently, in such a suitably constructed set P, we can interpret an arbitrarily large square grid graph on the vertex set {po,Pi, ■ ■ ■ ,Pk^-\\- Since the squre grid is a folklore basic example of unbounded clique-width [11], we get from Corollary 6 that the clique-width of such configurations P (with d = 2) is unbounded. □ Theorem 16 (10). Assume a point set P given alongside with a clique-width expression of width d. The minimum convex partition problem of P into < k convex faces is solvable in linear FPT time with respect to the parameter d + k. Proof. Let convhole(X) denote the MSO formula (3). We describe the existence of a partition into k convex faces as follows where the subformula convpartition checks whether the convex hulls of the sets Xi partition conv(P). For the latter, we will test the following three conditions: — for 1 < i, j < k, i 7^ j, we have Xi <2 Xj, 18 O. Qagirici, P. Hliněný F. Pokrývka and A. Sankaran — the boundaries of the polygons conv(Xi) and conv(Xj) do not cross (neither in a vertex, nor in the interior of an edge), and — every boundary edge of each conv(Xi) is, at the same time, a boundary edge of exactly one other of conv(Xj) or of conv(P). We hence first need to define in MSO logic when two points x, y of a strictly convex set Y C P form a boundary edge of conv(Y) in the counter-clockwise orientation from x to y. Analogously to (2), we write this as bdedge(Y, x, y) = x, y € Y A x 7^ y A Vz [(z € Y A z 7^ x, y) —> ordccw(x, y, z)]. Second, we define in MSO the fact that two straight line segments, xx' and yy' with distinct ends, cross each other in an interior point of both; ecross(x, x', y, y') = ( ordccw(x, y, y') ordccw(x', y, t/')) A ( ordccw(y, x, x1) <-/-> ordccw(y', x, a;')). The rest of the definition of convpartition is a routine combination of the presented MSO formulas. Finally, we finish by an application of the decision version of Theorem 7. □ Theorem 17 (11). Assume a polygonal terrain L given alongside with a clique-width expression of width d (defining both the successor relation and the order type of the vertices, cf. end of Section 2). The Segmented terrain guarding problem of L is solvable in linear FPT time with respect to the parameter d. Proof. Formally, we view L as a relational structure on the ground set P, over a vocabulary with three relations; ternary ordccw C Pa, binary terredge C P2 and unary canguard C P. As before, ordccw = fi{P) is interpreted as the order type of P, and terredge is interpreted as the successive pairs in the left-to-right ordering of points of P on L. Let terredge* denote the transitive closure of the successor relation terredge, which is easily expressed in MSO logic. Lastly, unary canguard is interpreted as the given subset Pi C P of allowable guard vertices. We construct a formula seguard(X) stating that every segment yy' of the terrain L is seen by a single vertex guard x of X, as follows Vy, y' [ terredge(y, y') —> 3x € X( ordccw(x, y, y') A nopeak(x, y, y'))] ■ The part ordccw(x, y, y') certifies that the segment yy' of the polygonal line L is (potentially) seen "from above" by a guard at x. The formula nopeak(x, y, y') then states that no part ("peak" z) of the terrain L between a guard at x and the segment yy' blocks the visibility, written as Vz[( terredge(y, y') A terredge*(y', z) A terredge* (z, x)) —> -1 ordccw(y', x, z)] A Vz [(terredge(y, y') A terredge* (x, z) A terredge* (z, y)) —> -1 ordccw(x, y, z)]. We then formulate seguard(X) A \/x € X canguard(x) to say that a guard set X is a valid solution. The optimization version (finding min-cardinaluty X) of Theorem 7 finishes the proof. □ Clique-Width of Point Configurations 19 Fig. 4. Guarding an art gallery: the four black vertex guards see all edges of the depicted polygon (each edge seen by a single guard), and 4 is the obvious necessary minimum. However, knowing only the order type of the polygon vertices, we cannot say whether there is a "blind spot" in the middle of the polygon (the depicted dotted spot) or not. Note on the Art gallery problem. We also briefly explain, why our approach to solving terrain guarding in Theorem 11 cannot be directly extended to the traditional and more general Art gallery (guarding) problem [24], not even in the adjusted case when each edge of the polygon is seen by a single vertex guard. When "guarding a terrain", the definition requires the guard set to see all points of the polygonal line defining that terrain (and then it comes for free that the guards also see every point "above" the terrain). On the other hand, the usual definition of the Art gallery problem requires the guards to see every interior point of the polygon in addition to all its boundary points. This aspect is important, since observing all boundary points does not exclude possible presence of "blind spots" in the interior of the polygon. With a simple example in Figure 4, we show that, even in our adjusted setting in which every boundary edge must be seen by a single guard, we cannot determine whether the interior of the polygon is guarded knowing just the order type n(P). Theorem 18 (12). Assume a polygon Q with vertex set P given as a relational structure consisting of the order type fi{P) and the counter-clockwise Hamil- 20 O. Cagirici, P. Hliněný F. Pokrývka and A. Sankaran tonian cycle of the edges of Q. Then the visibility graph of Q has an MSO interpretation in Q. Proof. Formally, we again view Q as a relational structure on the ground set P, over a vocabulary with two relations; ternary ordccw = fi(P) and binary poledge C P2. The relation poledge is interpreted as the edge relation of the counterclockwise directed cycle of the polygonal edges of Q. Recall that the visibility graph of Q has the same vertex set as Q and the edges are those line segments with ends in the vertices of Q which are disjoint from the complement of Q. Our aim is to define an MSO formula e{x,y) such that Q \= e{x,y) if and only if {x, y} is an edge of the visibility graph of Q. For that we recall the MSO formula ecross(x,x',y,y') from the proof of Theorem 16 above. Defining e is then a routine exercise using the following facts: — Consider a vertex x € P such that the incoming polygon edge to x is (x\, x) and the outgoing one is (a;, a^)- Then for any {x,y} to be a visibility edge of Q, the point y must lie in the clockwise orientation (non-strictly) from (x,xi) to (x,X'2). Written in MSO; 3xi, X2 (poledge(xi, x) Apoledge(x, X2) A -1 ordccw(x, x\, y) A - ^ ecross(x, y, z\, Z2)). — Conversely, if the previous two conditions are satisfied for each of x and y, then {x, y} is a visibility edge of Q. □