Jean-Lou De Carufel

Adrian Dumitrescu
email: dumitres@uwm.edu

Wouter Meulemans
email: w.meulemans@tue.nl

Tim Ophelders
email: ophelder@egr.msu.edu

Claire Pennarun
email: claire.pennarun@lirmm.fr

Csaba Toth
email: csaba.toth@csun.edu

Sander Verdonschot
email: sander@cg.scs.carleton.ca

Csaba D Tóth

Convex Polygons in Cartesian Products

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Can a convex polygon P in the plane be reconstructed from the projections of its vertices to the coordinate axes? Assuming that no two vertices of P share the same x-or y-coordinate, we arrive at the following problem: given two sets, X and Y , each containing n real numbers, does the Cartesian product X × Y support a convex polygon with n vertices? We say that X × Y contains a polygon P if every vertex of P is in X × Y ; and X × Y supports P if it contains P and no two vertices of P share an x-or y-coordinate. For short, we call the Cartesian product X × Y an n × n grid.

Not every n × n grid supports a convex n-gon. This is the case already for n = 5 (Figure 1). Several interesting questions arise: can we decide efficiently whether an n × n-grid supports a convex n-gon? How can we find the largest k such that it supports a convex k-gon? What is the largest k such that every n × n grid supports a convex k-gon? How many convex polygons does an n × n grid support, or contain? We initiate the study of these questions for convex polygons, and their higher dimensional variants for convex polyhedra.

Our Results. We first show that every n × n grid supports a convex polygon with (1 -o(1)) log n vertices1 ; this bound is tight up to a constant factor: there are n × n grids that do not support convex polygons with more than 4 log n vertices. We generalize our upper and lower bounds to higher dimensions, and show that every d-dimensional Cartesian product d i=1 Y i , where |Y i | = n and d is constant, contains Ω(log d-1 n) points in convex position; this bound is also tight apart from constant factors (Section 2). Next, we present polynomial-time algorithms to find a maximum supported convex polygon that is x-or y-monotone. We show how to efficiently approximate the maximum size of a supported convex polygon up to a factor of two (Section 3). Finally, we present tight asymptotic bounds for the maximum number of convex polygons supported by an n × n grid (Section 4). We conclude with open problems (Section 5).

Related Work. Erdős and Szekeres proved, as one of the first Ramsey-type results in combinatorial geometry [START_REF] Graham | Euclidean Ramsey theory[END_REF], that for every k ∈ N, a sufficiently large point set in the plane in general position contains k points in convex position. The minimum cardinality of a point set that guarantees k points in convex position is known as the Erdős-Szekeres number, f (k). They proved that

2 k-2 + 1 ≤ f (k) ≤ 2k-4 k-2 + 1 = 4 k(1-o(1)
) , and conjectured that the lower bound is tight [START_REF] Erdős | On some extremum problems in elementary geometry[END_REF]. The current best upper bound, due to Suk [START_REF] Suk | On the Erdős-Szekeres convex polygon problem[END_REF], is f (k) ≤ 2 k(1+o (1)) . In other words, every set of n points in general position in the plane contains (1 -o(1)) log n points in convex position, and this bound is tight up to lower-order terms.

In dimension d ≥ 3, the asymptotic growth rate of the Erdős-Szekeres number is not known. By the Erdős-Szekeres theorem, every set of n points in general position in R d contains Ω(log n) points in convex position (it is enough to find points whose projections onto a generic plane are in convex position). For every constant d ≥ 2, Károlyi and Valtr [START_REF] Károlyi | Configurations in d-space without large subsets in convex position[END_REF] and Valtr [START_REF] Valtr | Sets in R d with no large empty convex subsets[END_REF] constructed n-element sets in general position in R d in which no more than O(log d-1 n) points are in convex position. Both constructions are recursive, and one of them is related to high-dimensional Horton sets [START_REF] Valtr | Sets in R d with no large empty convex subsets[END_REF]. These bounds are conjectured to be optimal apart from constant factors. Our results establish the same O(log d-1 n) upper bound for Cartesian products, for which it is tight apart from constant factors. However our results do not improve the bounds for points in general position.

Algorithmically, one can find a largest convex cap in a given set of n points in R2 in O(n 2 log n) time by dynamic programming [START_REF] Edelsbrunner | Topologically sweeping an arrangement[END_REF], and a largest subset in convex position in O(n 3 ) time [START_REF] Chvátal | Finding largest convex subsets[END_REF][START_REF] Edelsbrunner | Topologically sweeping an arrangement[END_REF]. The same approach can be used for counting the number of convex polygons contained in a given point set [START_REF] Joseph | Counting convex polygons in planar point sets[END_REF]. While this approach applies to grids, it is unclear how to include the restriction that each coordinate is used at most once. On the negative side, finding a largest subset in convex position in a point set in R d for dimensions d ≥ 3 was recently shown to be NP-hard [START_REF] Giannopoulos | On the computational complexity of Erdős-Szekeres and related problems in R 3[END_REF].

There has been significant interest in counting the number of convex polygons in various point sets. Answering a question of Hammer, Erdős [START_REF] Erdős | Some more problems on elementary geometry[END_REF] proved that every set of n points in general position in R 2 contains exp(Θ(log 2 n)) subsets in convex position, and this bound is the best possible. Bárány and Pach [START_REF] Bárány | On the number of convex lattice polygons[END_REF] showed that the number of convex polygons in an n × n section of the integer lattice is exp O(n 2/3 ) . Bárany and Vershik [START_REF] Bárány | On the number of convex lattice polytopes[END_REF] generalized this bound to d-dimensions and showed that there are exp O(n d(d-1)/(d+1) ) convex polytopes in an n × • • • × n section of Z d . Note that the exponent is sublinear in n for every d ≥ 2. We prove that an n × n Cartesian product can contain exp(Θ(n))) convex polygons, significantly more than integer grids, and our bounds are tight up to polynomial factors.

Motivated by integer programming and geometric number theory, lattice polytopes (whose vertices are in Z d ) have been intensely studied; refer to [START_REF] Bárány | Random points and lattice points in convex bodies[END_REF][START_REF] Barvinok | Lattice points and lattice polytopes[END_REF]. However, results for lattices do not extend to arbitrary Cartesian products. Recently, several deep results have been established for Cartesian products in incidence geometry and additive combinatorics [START_REF] Orit | On the number of unit-area triangles spanned by convex grids in the plane[END_REF][START_REF] Orit | Polynomials vanishing on grids: The Elekes-Rónyai problem revisited[END_REF][START_REF] Orit | Polynomials vanishing on Cartesian products: The ElekesSzabó theorem revisited[END_REF][START_REF] Schwartz | Extensions of a result of Elekes and Rónyai[END_REF], while the analogous statements for points sets in general position remain elusive. We consider special types of convex polygons. Let P be a convex polygon with vertices ((x 1 , y 1 ), . . . , (x k , y k )) in clockwise order. We say that P is a convex cap if the x-or y-coordinates are monotonic, and a convex chain if both the x-and y-coordinates are monotonic. We distinguish four types of convex caps (resp., chains) based on the monotonicity of the coordinates as follows:

Definitions. A polygon P in R 2 is convex if all of
• convex caps come in four types { , , , }. • convex chains come in four types { , , , }. We have = ∩ , = ∩ , = ∩ , = ∩ .

Initial observations. It is easy to see that for n = 3, 4, every n × n grid supports a convex n-gon. However, there exists a 5 × 5 grid that does not support any convex pentagon (cf. Fig. 1). Interestingly, every 6 × 6 grid supports a convex pentagon.

Lemma 1. Every 6 × 6 grid X × Y supports a convex polygon of size at least 5.

Proof. Let X = X \ {min(X), max(X)} and Y = Y \ {min(Y ), max(Y )}. The 4 × 4 grid X × Y supports a convex chain P of size 3 between two opposite corners of X × Y . Then one xcoordinate x ∈ X and one y-coordinate y ∈ Y are not used by P . Without loss of generality, assume that P ∈ . Then the convex polygon containing the points of P and (x , min(Y )) and (max(X), y ) is a supported convex polygon of size 5 on X × Y .

2 Extremal Bounds for Convex Polytopes in Cartesian Products

Lower Bounds in the Plane

In this section, we show that for every n ≥ 3, every n × n grid supports a convex polygon with Ω(log n) vertices. The results on the Erdős-Szekeres number cannot be used directly, since they crucially use the assumption that the given set of points is in general position. An n × n section of the integer lattice is known to contain Θ(n) points in general position [START_REF] Appendix | On a problem of Heilbronn[END_REF], and this number is conjectured to be π

√ 3 n(1 + o(1)
) [START_REF] Guy | The no-three-in-line-problem[END_REF][START_REF] Weisstein | No-three-in-a-line-problem[END_REF]. However, this result does not apply to arbitrary Cartesian products. It is worth noting that higher dimensional variants for the integer lattice are poorly understood: it is known that an n × n × n section of Z 3 contains Θ(n 2 ) points no three of which are collinear [START_REF] Pór | No-three-in-line-in-3D[END_REF], but no similar statements are known in higher dimensions. We use a recent result from incidence geometry. Proof. Every n × n grid contains a set of Ω( n 2 / log n) = Ω(n/ √ log n) points in general position by applying Lemma 2 with N = n 2 and = n. Discarding points with the same x-or y-coordinate reduces the size by a factor at most 1 4 , so this asymptotic bound also holds when coordinates in X and Y are used at most once. By Suk's result [START_REF] Suk | On the Erdős-Szekeres convex polygon problem[END_REF], the grid supports a convex polygon with at least

(1 -o(1)) log(n/ √ log n) = (1 -o(1)) log n vertices.

Upper Bounds in the Plane

For the upper bound, we construct n × n Cartesian products that do not support large convex chains. For n = 8, such a grid is depicted in Figure 2.

Lemma 4. For every n ∈ N, there exists an n×n grid that does not contain more than 4( log n +1) points in convex position.

Proof. Let g(n) be the maximum integer such that for all n-element sets X, Y ⊂ R, the grid X × Y supports a convex polygon of size g(n); clearly g(n) is nondecreasing. Let k be the minimum integer such that n ≤ 2 k ; thus log n ≤ k and g(n) ≤ g(2 k ). We show that g(2 k ) ≤ 4(k + 1) and thereby establish that g(n) ≤ 4(k + 1). Assume w.l.o.g. that n = 2 k , and let X = {0, . . . , n -1}. For a k-bit integer m, let m i be the bit at its i-th position, such that m

= k-1 i=0 m i 2 i . Let Y = { k-1 i=0 m i (2n) i | 0 ≤ m ≤ n -1} (see Fig. 2). Both X and Y are symmetric: X = {max(X) -x | x ∈ X} and Y = {max(Y ) -y | y ∈ Y }.
Thus, it suffices to show that no convex chain P ∈ of size greater than k + 1 exists.

Consider two points, p = (x, y) and p = (x , y ), in X × Y such that x < x and y < y . Assume y = k-1 i=0 m i (2n) i and y = k-1 i=0 m i (2n) i . The slope of the line spanned by p and p is slope(p, p ) = k-1 i=0 (m i -m i )(2n) i /(x -x). Let j be the largest index such that m j = m j . Then y < y implies m j < m j , and we can bound the slope as follows:

slope(p, p ) ≥ (2n) j -j-1 i=0 (2n) i x -x > (2n) j -2(2n) j-1 n -1 = 2 • (2n) j-
≤ j i=0 (2n) i x -x ≤ j i=0 (2n) i 1 = (2n) j+1 -1 2n -1 < 2 • (2n) j .
Hence, slope(p, p

) ∈ I j = (2 • (2n) j-1 , 2 • (2n) j ).
Let us define the family of intervals I 0 , I 1 , . . . , I k-1 analogously, and note that these intervals are pairwise disjoint. Suppose that some convex chain P ∈ contains more than k + 1 points. Since the slopes of the first k + 1 edges of P decrease monotonically, by the pigeonhole principle, there must be three consecutive vertices p = (x, y), p = (x , y ), and p = (x , y ) of P such that both slope(p, p ) and slope(p , p ) are in the same interval, say I j . Assume that y = k-1 i=0 m i (2n) i , y = k-1 i=0 m i (2n) i+1 , and y = k-1 i=0 m i (2n) i+1 . Then j is the largest index such that m j = m j , and also the largest index such that m j = m j . Because m < m < m , we have m j < m j < m j , which is impossible since each of m j , m j and m j is either 0 or 1.

Hence, X × Y does not contain any convex chain in of size greater than k + 1. Analogously, every convex chain in , , or has at most k + 1 vertices. Consequently, X × Y does not contain more than 4(k + 1) points in convex position.

Upper Bounds in Higher Dimensions

We construct Cartesian products in R d , for d ≥ 3, that match the best known upper bound O(log d-1 n) for the Erdős-Szekeres numbers in d-dimensions for points in general position. Our construction generalizes the ideas from the proof of Lemma 4 to d-space. Lemma 5. Let d ≥ 2 be an integer. For every integer n ≥ 2, there exist n-element sets

Y i ⊆ R for i = 1, . . . , d, such that the Cartesian product Y = d i=1 Y i does not contain more than O(log d-1 n) points in convex position.
Proof. We construct point sets recursively. For d = 2, the result follows from Lemma 4. For integers d ≥ 3 and 0 ≤ i ≤ j, we define S d (i, j) as a Cartesian product of d sets, where the first d -1 sets have 2 j elements and the last set has 2 i elements. We then show that S d (i, j) does not support any Figure 3: A polyhedron conv(P ) in R 3 , whose projection conv(P ) proj is a rectangle. Seven points in P are projected onto the four vertices of conv(P ) proj . Overall the silhouette of P contains 12 points. Red (blue) vertices are upper (lower); the purple point is both upper and lower.

full-dimensional convex polyhedron with more than 2 d 2 -d-1 • i • j d-2 vertices (there is no restriction on lower-dimensional convex polyhedra).

To initialize the recursion, we define boundary values as follows: For every integer j ≥ 0, let S 2 (j, j) be the 2 j × 2 j grid defined in the proof of Lemma 4 that does not contain more than 4(j + 1) points in convex position. Note that every line that contains 3 or more points from S 2 (j, j) is axis-parallel (this property was not needed in the proof of Lemma 4). Assume now that d ≥ 3, and S d-1 (j, j) has been defined for all j ≥ 0; and every k-dimensional flat containing k + 1 or more points is axis-aligned for all k = 1, . . . , d. Let j be a nonnegative integer. We now construct S d (i, j) for all integers 0 ≤ i ≤ j as follows.

Let S d (0, j) = S d-1 (j, j) × {0}. For i = 1, . . . , j, we define S d (i, j) as the disjoint union of two translates of S d (i -1, j). Specifically, let S d (i, j) = A ∪ B, where A = S d (i -1, j) and B = A + λ i d e d , where λ i d > 0 is sufficiently large (as specified below) and algebraically independent from the coordinates of S d (i, j), such that every k-dimensional flat containing k + 1 or more points of A ∪ B is axis-aligned for all k = 1, . . . d.

Let P ⊂ S d (i, j) be a full-dimensional set in convex position. The orthogonal projection of conv(P ) to the horizontal hyperplane x d = 0 is a convex polytope in R d-1 that we denote by conv(P ) proj ; refer to Fig. 3. The silhouette of P is the subset of vertices whose orthogonal projection to x d = 0 lies on the boundary of conv(P ) proj . Since no three points in P are collinear, then at most two points in P are projected to a same point. A point p ∈ P is an upper (resp., lower ) vertex if P lies in the closed halfspace below (resp., above) some tangent hyperplane of conv(P ) at p (a point in p may be both upper and lower vertex).

We prove, by double induction on d and i, the following:

Claim 1. If P ⊂ S d (i, j) is a full-dimensional set in convex position, then P contains at most 2 d(d-1) • i • j d-2 upper (resp.
, lower) vertices of conv(P ).

For d = 2 and i = j, this holds by definition (cf. Lemma 4). For i = 0, the set S d (0, j) = S d-1 (j, j) × {0} lies in a horizontal hyperplane in R d , and so it is not full-dimensional, hence the claim vacuously holds. By induction, S d-1 (j, j) contains at most 2

(d-1)(d-2) • j • j d-3 upper (resp., lower) vertices in R d-1 , hence S d (0, j) has at most 2 • 2 (d-1)(d-2) • j • j d-3 extreme points in R d . For i = 1, the set S d (1, j) is the disjoint union of A = S d (0, j) and B = S d (0, j) + λ 1 d e d . Every upper (resp., lower) vertex of S d (1, j) is an extreme vertex in A or B, hence S d (1, j) contains at most 4 • 2 (d-1)(d-2) • j d-2 = 2 d 2 -3d+4 • j d-2 < 2 d 2 -d • 1 • j d-2
upper (resp., lower) vertices, as required, where we used that d ≥ 3. Assume that d ≥ 3, 2 ≤ i ≤ j, and the claim holds for S d-1 (j, j) and S d (i -1, j). We prove the claim for S d (i, j). Recall that S d (i, j) is the disjoint union of two translates of S d (i -1, j), namely A = S d (i -1, j) and B = S d (i -1, j) + λ i d e d . Let P ⊂ S d (i, j) be a full-dimensional set. We partition the upper vertices in P as follows. Let P 0 ⊂ P be the set of upper vertices whose orthogonal projection to x d = 0 is a vertex of conv(P ) proj . For k = 1, . . . , d -1, let P k ⊂ P be the set of upper vertices whose orthogonal projection to x d = 0 lies in the relative interior of a k-face of conv(P ) proj . By construction, only axis-aligned faces can contain interior points, and a (d -1)-dimensional polytope has at most d-1 k axis-aligned k-faces, where d-

1 k=1 d-1 k < 2 d-1
. The orthogonal projection of S d (i, j) to x d = 0 is S d-1 (j, j), and the orthogonal projection

P proj 0 of P 0 is the vertex set of the (d -1)-dimensional convex polyhedron S d-1 (j, j). By induction, |P 0 | ≤ 2 • 2 (d-1)(d-2) • j • j d-3 = 2 d 2 -3d+3 j d-2
. We show the following.

Claim 2. For every axis-aligned face F of conv(P ) proj , the set of upper vertices that project to the interior of F is contained in either A or B.

Let F be an axis-aligned k-face of conv(P ) proj for k ∈ {1, 2, . . . , d -1}. Let P (F ) ⊂ P be the set of upper vertices whose orthogonal projection lies in the interior of F , and let P (∂F ) be the set of upper vertices whose orthogonal projection lies in the boundary of F . Let P (∂F ) proj be the orthogonal projection of P (∂F ) to the hyperplane x d = 0. Consider the point set P = P (∂F ) proj ∪ P (F ), and observe that if P (F ) = ∅, then it is a vertex set of a (k + 1)-dimensional polytope in which all vertices are upper. It remains to show that P (F ) ⊆ A or P (F ) ⊆ B. Suppose, for the sake of contradiction, that P (F ) contains points from both A and B. Let p a be a vertex in P (F ) with the maximum x d -coordinate. The 1-skeleton of conv(P ) contains a x d -monotonically decreasing path from p a to an x d -minimal vertex in P . Let p b be the neighbor of p a along such a path. Then p b ∈ B by the choice of p a . Every hyperplane containing p a and p b partitions P (∂F ) proj , in particular the tangent hyperplane of P containing the edge p a p b , which is a contradiction.

We can now finish the proof of Claim 1. By induction on S d (i -1, j), we have

|P k | ≤ d -1 k • 2 k(k-1) • (i -1) • j k-1 .
Altogether, the number of upper vertices is

d-1 k=0 |P k | ≤ 2 d 2 -3d+3 j d-2 + d-1 k=1 d -1 k 2 k(k-1) • (i -1) • j k-1 < 2 d(d-1) j d-2 + 2 d-1 • 2 (d-1)(d-2) • (i -1) • j d-2 < 2 d(d-1) • i • j d-2 ,
as required, where we used the binomial theorem and the inequality 3 ≤ d.

Lower Bound in Higher Dimensions

The proof technique in Section 2.1 is insufficient for establishing a lower bound of Ω(log d-1 n) in R d for d ≥ 3. While a d-dimensional n × . . . × n grid contains Ω(n δ ) points in general position for some δ = δ(d) > 0 [START_REF] Cardinal | A on independent hyperplanes and general position subsets in d-space[END_REF], the current best lower bound for the Erdős-Szekeres number for n points in general position in R d is Ω(log n); although it is conjectured to be Ω(log d-1 n). Instead, we rely on the structure of Cartesian products and induction on d.

We say that a strictly increasing sequence of real numbers A = (a 1 , . . . , a n ), has the monotone differences property (for short, A is MD), if

• a i+1 -a i > a i -a i-1 for i = 2, . . . , n -1, or • a i+1 -a i < a i -a i-1 for i = 2, . . . , n -1.
Further, the sequence A is r-MD for some r > 1 if

• a i+1 -a i ≥ r(a i -a i-1 ) for i = 2, . . . , n -1, or • a i+1 -a i ≤ (a i -a i-1 )/r for i = 2, . . . , n -1.
A finite set X ⊆ R is MD (resp., r-MD) if its elements arranged in increasing order form an MD (resp., r-MD) sequence. These sequences are intimately related to convexity: a strictly increasing sequence A = (a 1 , . . . , a n ) is MD if and only if there exists a monotone (increasing or decreasing) convex function f : R → R such that a i = f (i) for all i = 1, . . . , n. MD sets have been studied in additive combinatorics [START_REF] Elekes | Convexity and sumsets[END_REF][START_REF] Hegyvári | On consecutive sums in sequences[END_REF][START_REF] Orit | On the number of unit-area triangles spanned by convex grids in the plane[END_REF][START_REF] Schoen | On sumsets of convex sets[END_REF].

We first show that every n-element set X ⊆ R contains an MD subset of size Ω(log n), and this bound is the best possible (Corollary 7). In contrast, every n-term arithmetic progression contains an MD subsequence of Θ( √ n) terms: for example (0, . . . , n -1) contains the subsequence (i 2 : i = 0, . . . , √ n -1 ). We then show that for constant d ≥ 2, the d-dimensional Cartesian product of n-element MD sets contains Θ(n d-1 ) points in convex position. The combination of these results immediately implies that every n × . . . × n Cartesian product in R d contains Ω(log d-1 n) points in convex position.

The following lemma for 2-MD sequences (satisfying the so-called doubling differences condition [START_REF] David | The classification of the order indiscernibles of real closed fields and other theories[END_REF]) was proved in [6, Lemma 4.1] (see also [START_REF] Conlon | Ramsey-type results for semi-algebraic relations[END_REF] for related recent results). We include an elementary proof for completeness. Lemma 6. Every set of n real numbers contains a 2-MD subset of size (log n)/2 + 1.

Proof. Let X = (x 0 , . . . , x n-1 ) be a strictly increasing sequence. Assume w.l.o.g. that n = 2 + 1 for some ∈ N. We construct a sequence of nested intervals

[a 0 , b 0 ] ⊃ [a 1 , b 1 ] ⊃ . . . ⊃ [a , b ]
such that the endpoints of the intervals are in X and the lengths of the intervals decrease by factors of 2 or higher, that is, b i -a i ≤ (b i-1 -a i-1 )/2 for i = 1, . . . , .

We start with the interval [a 0 , b 0 ] = [x 0 , x n-1 ]; and for every i = 0, . . . , -1, we divide [a i , b i ] into two intervals at the median, and recurse on the shorter interval.

By partitioning [a i , b i ] at the median, the algorithm maintains the invariant that [a i , b i ] contains 2 -i + 1 elements of X. Note that for every i = 1, . . . , , we have either (a i-1 = a i and b i-1 < b i ) or (a i-1 = a i and b i < b i-1 ). Consequently, the sequences A = (a 0 , a 1 , . . . , a ) and B = (b , b -1 , . . . , b 0 ) both increase (not necessarily strictly), and at least one of them contains at least 1 + /2 distinct terms. Assume w.l.o.g. that A contains at least 1 + /2 distinct terms. Let C = (c 0 , . . . , c k ) be the maximal strictly increasing subsequence of A. Then k ≥ /2 = (log n)/2 . We show that C is a 2-MD sequence. Let i ∈ {1, . . . , k -1}. Assume that c i = a j = . . . = a j for consecutive indices j, . . . j . Then c i-1 = a j-1 , c i = a j , and c i+1 = a j +1 . By construction,

c i ∈ [a j-1 , b j-1 ] = [c i-1 , b j ] such that c i -c i-1 ≥ b j -c i . Similarly, c i+1 ∈ [a j , b j ] = [c i , b j ] such that c i+1 -c i ≥ b j -c i+1 . However, [a j , b j ] ⊃ [a j , b j ]. As required, this yields c i -c i-1 ≥ b j -c i = b j -a j ≥ b j -a j = (b j -c i+1 ) + (c i+1 -c i ) ≥ c i+1 -c i 2 .
The lower bound in Lemma 6 is tight apart from constant factors even if we ask for an MD subsequence (rather than a 2-MD subsequence). We show how to use Lemma 6 to establish a lower bound in the plane. While this approach yields worse constant coefficients than Lemma 3, its main advantage is that it generalizes to higher dimensions (see Lemma 10 below). Lemma 8. The Cartesian product of two MD sets, each of size n, supports n points in convex position.

Proof. Let A = {a 1 , . . . , a n } and B = {b 1 , . . . , b n } be MD sets such that a i < a i+1 and b i < b i+1 for i = 1, . . . , n -1. We may assume, by applying a reflection if necessary, that a i+1 -a i < a i -a i-1 and b i+1 -b i < b i -b i-1 , for i = 2, . . . , n -1 (see Fig. 5).

We define P ⊂ A × B as the set of n points (a i , b j ) such that i + j = n + 1. By construction, every horizontal (vertical) line contains at most one point in P . Since the differences a i -a i-1 are positive and strictly decrease in i; and the differences b -i -b -i-1 are negative and their absolute values strictly increase in i, the slopes (b -i -b -i-1 )/(a i -a i-1 ) strictly decrease, which proves the convexity of P . Lemma 9. The Cartesian product of three MD sets, each of size n, supports (hence also contains)

n+1 2
points in convex position. . . , c n } be MD sets, where the elements are labeled in increasing order. We may assume, by applying a reflection in the x-, y-, or z-axis if necessary, that

a i+1 -a i < a i -a i-1 , b i+1 -b i < b i -b i-1 , c i+1 -c i < c i -c i-1 , for i = 2, . . . , n -1. For i, j, k ∈ {1, . . . , n], let p i,j,k = (a i , b j , c k ) ∈ A × B × C. We can now let P = {p i,j,k : i + j + k = n + 2}. It is clear that |P | = n i=1 i = n+1 2 .
We let P = P ∪ {p 1,1,1 } and show that the points in P are in convex position.

By Lemma 8, the points in P lying in the planes x = a 1 , y = b 1 , and z = c 1 are each in convex position. These convex (n + 1)-gons are faces of the convex hull of P , denoted conv(P ). We show that the remaining faces of conv(P ) are the triangles T i,j,k spanned by p i,j,k , p i,j+1,k-1 , and p i+1,j,k-1 ; and the triangles T i,j,k spanned by p i,j,k , p i,j-1,k+1 , and p i-1,j,k+1 .

The projection of these triangles to an xy-plane is shown in Fig. 5. By construction, the union of these faces is homeomorphic to a sphere. It suffices to show that the dihedral angle between any two adjacent triangles is convex. Without loss of generality, consider triangle T i,j,k , which is adjacent to (up to) three other triangles: T i+1,j,k-1 , T i,j+1,k-1 , and T i+1,j+1,k-2 . Consider first the triangles T i,j,k and T i+1,j+1,k-2 . They share the edge p i+1,j-1,k+1 p i-1,j+1,k+1 , which lies in the xy-plane z = c k+1 . The orthogonal projections of these triangles to an xy-plane are congruent, however their extents in the z-axis are c i+1 -c i and c i -c i-1 , respectively. Since c i+1 -c i < c i -c i-1 , their diheral angle is convex. Similarly, the dihedral angles between T i,j,k and T i+1,j,k-1 (resp.,

T i,j+1,k-1 ) is convex because a i+1 -a i < a i -a i-1 and b i+1 -b i < b i -b i-1 .
The proof technique of Lemma 9 generalizes to higher dimensions: Lemma 10. For every constant d ≥ 2, the Cartesian product of d MD sets, each of size n, supports Ω(n d-1 ) points in convex position.

Proof. We proceed by induction on d. For d = 2, 3, Lemmas 8-9 prove the claim. Assume that d ≥ 4, and the claim holds in lower dimensions. For every i = 1, . . . , d, let A i = {a i,1 < . . . < a i,n } ⊂ R be an MD set such that the elements are labeled in increasing order. We may assume w.l.o.g. that the differences between consecutive elements in A i strictly decrease for all i = 1, . . . , d.

For every vector

v = (v 1 , . . . , v d ) ∈ {1, . . . , n} d , let p v = (a 1,v 1 , a 2,v 2 , . . . , a d,v d ) ∈ d i=1 A i . Let P = {p v : d i=1 v i = n + d -1}. It is easy to see that |P | = Θ(n d-1
). Let P = P ∪ {p 1,...,1 }. We show that the points in P are in convex position. By induction, the points of P lying in the hyperplanes x i = a i,1 , for i = 1, . . . , d, are each in convex position, hence they each define (d -1)-dimensional facets of conv(P ). We define additional (d -1)-dimensional facets such that the union of these facets is homeomorphic to S d-1 , and the union of their vertex sets is P . We then verify that the dihedral angles between adjacent facets are convex, which implies that these are the facets of conv(P ), and consequently P is in convex position.

For every vector v ∈ {1, . . . , n -1} d , consider the hyperrectangle

r v = d i=1 [a i,v i , a i,v i +1 ]
. Note that the vertices of each r v are in d i=1 A i , and the hyperrectangles jointly tile the bounding box

d i=1 [a i,1 , a i,n ]. For every r v , let F v = conv(P ∩ r v )
, that is, the convex hull of vertices of r v that are in P . By construction, every F v is at most (d -1)-dimensional (possibly empty). Let F be the set of all (d -1)-dimensional sets F v ; we call them facets. By construction, the union of the facets in F, together with the facets in the hyperplanes x i = a i,1 for i = 1, . . . , d, is homeomorphic to the sphere S d-1 . Any two adjacent facets in f u , f w ∈ F lie in two adjacent hyperrectangles, r u and r w , whose common boundary is (d -1)-dimensional, say, in the hyperplane x i = a i,j for some j = 2, . . . , n -1. The facet f u (resp., f w ) is parallel to the (d -1)-simplex spanned by the d vertices of r u (resp., r w ) adjacent to p u (resp., p w ). Since A i is MD, we have a i,j+1 -a i,j < a i,j -a i,j-1 . These are the i-th extents of r u and r w ; their remaining d -1 extents are the same. Consequently, the dihedral angle between f u and f w is convex, as required.

Algorithms

In this section, we describe polynomial-time algorithms for (i) finding convex chains and caps of maximum size; and (ii) approximating the maximum size of a convex polygon; where these structures are supported by a given grid. The main challenge is to ensure that the vertices of the convex polygon (resp., cap or chain) have distinct x-and y-coordinates. The coordinates of a point p ∈ X × Y are denoted by p.x and p.y.

As noted in Section 1, efficient algorithms are available for finding a largest convex polygon or convex cap contained in a planar point set. Edelsbrunner and Guibas [11, Thm. 5.1.2] use the dual line arrangement of N points in the plane and dynamic programming to find the maximum size of a convex cap in in O(N 2 ) time and O(N ) space; the same bounds hold for , , and . A longest convex cap can be also returned in O(N 2 log N ) time and O(N log N ) space. It is straightforward to adapt their algorithm to find the maximum size of a convex cap in , and report a longest such chain within the same time and space bounds. Since x-and y-coordinates do not repeat in a convex chain, we obtain the following.

Corollary 11. In a given n×n grid, the maximum size of a supported convex chain can be computed in O(n 4 ) time and O(n 2 ) space; and a supported convex chain of maximum size can be computed in O(n 4 log n) time and O(n 2 log n) space.

We make use of the following general observation: Observation 12. If a supported convex polygon P is in a set , , , , , , , or , then every subsequence of P is in the same set. That is, these classes are hereditary.

Convex caps

For computing the maximum size of a convex cap in , we need to be careful to use each ycoordinate at most once. We design an algorithm that finds the maximum size of two convex chains that use distinct y-coordinates by dynamic programming. Specifically, for two edges l = (l 1 , l 2 ) and r = (r 1 , r 2 ), we compute the maximum total size C(l, r) of a pair of chains A ∈ and B ∈ such that their vertices use distinct y-coordinates and such that the last two vertices of A are l 1 and l 2 (or A = (l 1 ) if l 1 = l 2 ), and the first two vertices of B are r 1 and r 2 (or B = (r 1 ) if r 1 = r 2 ). We use the dynamic programming algorithm of [START_REF] Edelsbrunner | Topologically sweeping an arrangement[END_REF] to find L(p 1 , p 2 ) (resp., R(p 1 , p 2 )), the size of a largest convex chain P in (resp., ), ending (resp., starting) with vertices p 1 and p 2 , or

P = (p 1 ) if p 1 = p 2 .
The desired quantity C(l, r) can now be computed by dynamic programming. By Observation 12, we can always safely eliminate the highest vertex of the union of the two chains, to find a smaller subproblem, as this vertex cannot be (implicitly) part of the optimal solution to a subproblem. In particular, if l is a single vertex and it is highest, we can simply use the value of R(r 1 , r 2 ), incrementing it by one for the one vertex of l. Analogously, we handle the case if r is or both l and r are a single vertex. The interesting case is when both chains end in an edge. Here, we observe that we can easily check whether l and r use unique coordinates. If not, then this subproblem is invalid; otherwise, we may find a smaller subproblem by eliminating the highest vertex and comparing all possible subchains that could lead to it.

With the reasoning above, we obtain the recurrence below; see Fig. 6(a-c) for illustration. The first case eliminates invalid edges, and edge pairs that use a y-coordinate more than once. In all remaining cases, we assume that l ∈ , r ∈ , and l and r use distinct y-coordinates.

C(l, r) =                        -∞ if l 1 = l 2 and l / ∈ , or r 1 = r 2 and r / ∈ , or {l 1 .y, l 2 .y} ∩ {r 1 .y, r 2 .y} = ∅ 2 otherwise, if l 1 = l 2 and r 1 = r 2 L(l 1 , l 2 ) + 1 otherwise, if r 1 = r 2 and l 2 .y < r 1 .y R(r 1 , r 2 ) + 1 otherwise, if l 1 = l 2 and l 2 .y > r 1 .y max (v,l 1 ,l 2 )∈ or v=l 1 C((v, l 1 ), r) + 1 otherwise, if l 2 .y > r 1 .y max (r 1 ,r 2 ,v)∈ or v=r 1 C(l, (r 2 , v)) + 1 otherwise, l 2 .y < r 1 .y. Let E = (X × Y ) 2 denote
the number of pairs (edges) in the grid, from which we take l and r. As |E| = O(n 4 ), we can compute C(l, r) for all l and r in O(|E| 2 |X × Y |) = O(n 10 ) time and O(|E| 2 ) = O(n 8 ) space. With C(l, r), we can easily find the size of a maximum size cap P in , using the observation below, and analogous observations for the special case k = 1 and/or = 1 (see Fig. 6(d)).

r 1 r 2 l 1 l 2 r 1 = r 2 l 1 l 2 (a) (b) r 1 r 2 l 1 l 2 v r 1 r 2 l 1 l 2 (c) (d)
Figure 6: Illustration for the cases of C(l, r). (a) Invalid configuration, as r 2 .y = l 2 .y. (b) r is a single point above l 2 .y, so we look for the longest chain ending in l. (c) Removing the topmost point (from l in this case), testing all valid possible v to find the longest chain. Note that the left and right chain may not complete to a cap -this is checked separately. (d) We need to test only whether l and r make a cap (purple dotted line) to check whether the C(l, r) entry should be considered.

Observation 13. If A = (a 1 , . . . , a k ) ∈ B = (b 1 , . . . , b ) ∈ with k ≥ 2, ≥ 2 and (a k-1 , a k , b 1 , b 2 ) ∈
and A and B use distinct y-coordinates, then (a 1 , . . . , a k , b 1 , . . . , b ) lies in and has size k + .

Note that the condition (a

k-1 , a k , b 1 , b 2 ) ∈ implies that the x-coordinates are disjoint.
Lemma 14. For a given n × n grid, a supported convex cap of maximum size can be computed in O(n 10 ) time and O(n 8 ) space.

Convex n-chains and n-caps

If we are solely interested in deciding whether the grid X × Y , where |X| = |Y | = n, supports a convex chain or cap with precisely n vertices, we can improve upon the previous algorithms considerably. Let X = {x 1 , . . . , x n } and Y = {y 1 , . . . , y n } with x i < x i+1 and y i < y i+1 . To test whether there is a chain of size n in , it suffices to test whether the chain ((x 1 , y 1 ), . . . ,

(x n , y n )) is in , in O(n) time.
To test whether there is a supported convex cap of size n in , we adapt the algorithm of Lemma 14. Suppose P is a cap of of size n, with A P and B P its maximal components in and in respectively. Then P uses all coordinates of X, which restricts the types of chains A P and B P considerably. In particular C(l, r) can be modified to consider only edges l and r that use consecutive x-coordinates.

For 1 < k < n consider the subchains A k ∈ and B k ∈ of A P and B P consisting only of vertices with y-coordinate at most y k . These chains have length k in total and use all of the coordinates {y 1 , . . . , y k }. Let (l 1 , l 2 ) be the last edge of A k and let (r 1 , r 2 ) be the first edge of B k . Then the coordinates y k-1 and y k are used by l, or by r, or by l 2 and r 1 . Moreover, since the total length of A k and B k is k, there are n -k unused X-coordinates between l 2 and r 1 , so if l 2 .x = x i , then

Approximations

Although computing the maximum size of a supported convex polygon remains elusive, we can easily devise a constant-factor approximation algorithm by eliminating duplicate coordinates as follows.

Compute a maximum size convex polygon P (possibly with duplicate coordinates) in a given n × n grid in O(n 6 ) time and O(n 2 ) space [START_REF] Edelsbrunner | Topologically sweeping an arrangement[END_REF]Thm. 5.1.3]. Define a conflict graph on the vertices of P , where two vertices are in conflict if they share an x-or y-coordinate. Since each conflict corresponds to a horizontal or vertical line, the conflict graph has maximum degree at most 2 and contains no odd cycles, hence it is bipartite. One of the two sets in the bipartition contains at least half of the vertices of P without duplicate coordinates, and so it determines a supported convex polygon. Since P has O(n) vertices, the conflict graph can be computed in O(n) time. Overall, we obtain a

The Maximum Number of Convex Polygons

Let F (n) be the maximum number of convex polygons that can be present in an n × n grid, with no restriction on the number of times each coordinate is used. Let G(n) be this number where all 2n grid lines are used (i.e., each grid line contains at least one vertex of the polygon). Let F (n) and Ḡ(n) be the corresponding numbers where each grid line is used at most once (so F (n) counts the maximum number of supported convex polygons). By definition, we have

F (n) ≥ G(n) ≥ Ḡ(n) and F (n) ≥ F (n) ≥ Ḡ(n) for all n ≥ 2.
We prove the following theorem, in which the Θ * (.) notation hides polynomial factors in n.

Theorem 15. The following bounds hold:

F (n) = Θ * (16 n ), F (n) = Θ * (9 n ), G(n) = Θ * (9 n ), Ḡ(n) = Θ * (4 n ).

Upper bounds

We first prove that F (n) = O(n • 16 n ) by encoding each convex polygon in a unique way, so that the total number of convex polygons is bounded by the total number of encodings. Recall that a convex polygon P can be decomposed into four convex chains P , P , P , P , with only extreme vertices of P appearing in multiple chains. Let P = P ∪ P and P = P ∪ P . To encode P , we assign the following number to each of the 2n grid lines (see Fig. 7 for an example): 0 if is not incident on any vertex of P , 3 if is incident on multiple vertices of P , 1 if is incident on one vertex of P and that vertex lies on P if is horizontal, or on P if is vertical, and 2 otherwise.

In addition, we record the index of the horizontal line containing the leftmost vertex of P (pick the topmost of these if there are multiple leftmost points). Since each of the 2n grid lines is assigned one of 4 possible values, and there are n horizontal lines, the total number of encodings is O(n • 4 2n ) = O(n • 16 n ). All that is left to show is that each encoding corresponds to at most one convex polygon.

First, observe that if P is a convex chain, say in , then the set of grid lines containing a vertex of P uniquely defines P : since both coordinates change monotonically, the i-th vertex of P must be the intersection of the i-th horizontal and vertical lines. So all we need to do to reconstruct P is to identify the set of lines that make up each convex chain.

Since we know the location of the (topmost) leftmost vertex of P , we know where P starts. Every horizontal line above this point labelled with a 1 or 3 must contain a vertex of P ; let k be the number of such lines. Since the x-coordinates are monotonic as well, P ends at the k-th vertical line labelled with a 2 or 3. The next chain, P , starts either at the end of P , if the horizontal line is labelled with a 1, or at the intersection of this horizontal line with the next vertical line labelled with a 2 or 3, if this horizontal line is labelled with a 3. We can find the rest of the chains in a similar way. Thus,

F (n) = O(n • 16 n ).
The upper bounds for F (n), G(n), and Ḡ(n) are analogous, except that certain labels are excluded. For the number of supported convex polygons F (n), each grid line is used at most once, which means that the label 3 cannot be used. Thus, F

(n) = O(n • 3 2n ) = O(n • 9 n ).
Similarly, for G(n), all grid lines contain at least one vertex of the polygon, so the label 0 cannot be used. Therefore G

(n) = O(n • 3 2n ) = O(n • 9 n ).
Finally, for Ḡ(n), every grid line contains exactly one vertex of the polygon, so neither 0 nor 3 can be used as labels. This gives Ḡ

(n) = O(n • 2 2n ) = O(n • 4 n ) possibilities.

Lower bounds

Assume that n = 2m + 3, where m ∈ N satisfies suitable divisibility conditions, as needed. All four lower bounds use the same grid, constructed as follows (see Fig. 8). X = {1, . . . , n -1} Y -= {y 1 , . . . , y m+2 }, where

y i = n i Y = Y -∪ Y + Y + = {z 1 , . . . , z m+2 }, where z i = 2 • y m+2 -y i
Note that this results in an (n -1) × (n -1) grid, since y m+2 = z m+2 . To obtain an n × n grid, we duplicate the median grid lines in both directions and offset them by a sufficiently small distance ε > 0. The resulting grid has the property that any three points p, q, r in the lower half X × Y -with x p < x q < x r and y p < y q < y r make a left turn at q. To see this, suppose that y p = n i , y q = n j , and y r = n k , for some 1 ≤ i < j < k ≤ n. Then the slope of pq is strictly smaller than the slope of qr, since

slope(qr) = n k -n j x r -x q ≥ n j+1 -n j n -1 = n j > n j -n i 1 ≥ n j -n i x q -x p = slope(pq).
Thus, any sequence of points with increasing x-and y-coordinates in the lower half is in . By symmetry, such a sequence in the upper half X × Y + is in . Analogously, points with increasing x-coordinates and decreasing y-coordinates are in if they are in the lower half and if they are in the upper half. We first derive lower bounds on Ḡ(n) and G(n) by constructing a large set of convex polygons that use each grid line at least once. Then we use these bounds to derive the bounds on F (n) and F (n). The polygons we construct all share the same four extreme vertices, which lie on the intersections of the grid boundary with the duplicated median grid lines. Specifically, the leftmost and rightmost vertices are the intersections of the duplicate horizontal medians with the left and right boundary, and the highest and lowers vertices are the intersections of the duplicate vertical medians with the top and bottom boundary. Since each of these median lines now contain a vertex, we can choose additional vertices from the remaining 2m grid lines in each direction.

To construct each polygon, select m/2 vertical grid lines left of the median to participate in the bottom chain, and do the same right of the median. Likewise, select m/2 horizontal grid lines above and below the median, respectively, to participate in the left chain. The remaining grid lines participate in the other chain (top or right). This results in a polygon with m/2 vertices in the four extreme vertices of Z 0 , and an arbitrary subset of the remaining 4n -8 grid points in ∂conv(Z 0 ). There are 2 4n-8 = Ω(16 n ) such subsets, and the lower bound W (n) = Ω(16 n ) follows.

To show that W (n) = O * (16 n ), we modify the previous encoding used to show that F (n) = O * (16 n ). While the four grid lines along the boundary of the bounding box of P can be incident to arbitrarily many vertices, we still use at most two vertices for each such line, namely at most two extreme vertices. For each weakly convex polygon P , record the at most 8 extreme vertices incident to ∂B together with a vector (sequence) of length 2n: n elements corresponding to the horizontal lines (from the lowest to the highest), and n elements corresponding to the vertical lines (from left to right). As previously, we encode each grid line by an element of {0, 1, 2, 3}, where 3 stands for a line incident to at least two vertices. By (weak) convexity, a grid line can be incident to 3 or more vertices of P only if it is one of the four lines along the bounding box of P .

From the recorded information, we can reconstruct a weakly convex polygon in the n × n grid. Consequently, the number of convex polygons in the grid is bounded from above by the number of encodings, namely W (n) = O(n 8 • 4 2n ) = O(n 8 • 16 n ) = O * (16 n ). We summarize the bounds we have obtained in the following.

Theorem 16. Let W (n) denote the maximum number of weakly convex polygons that can be present in an n × n grid. Then W (n) = Ω(16 n ) and W (n) = O * (16 n ).

Conclusions

We studied combinatorial properties of convex polygons (resp., polytopes) in Cartesian products in d-space. Similar questions for point sets in general position or for lattice polygons (resp., polytopes) have been previously considered. We showed that every n × . . . × n Cartesian product in R d contains Ω(log d-1 n) points in convex position, and this bound is the best possible. Our upper bound matches previous bounds [START_REF] Károlyi | Configurations in d-space without large subsets in convex position[END_REF][START_REF] Valtr | Sets in R d with no large empty convex subsets[END_REF] for points in general position, which are conjectured to be tight. Our lower bound, however, does not yield any improvement for points in general position. In contrast, an n × . . . × n section of the integer lattice Z d contains significantly more, namely Θ(n d(d-1)/(d+1) ), points in convex position [START_REF] Andrews | A lower bound for the volume of strictly convex bodies with many boundary lattice points[END_REF].

The maximum number of convex polygons in an n × n Cartesian product is F (n) = Θ * (16 n ). This bound is tight up to polynomial factors, and is significantly larger than the corresponding bound in an n × n section of the integer lattice [START_REF] Bárány | On the number of convex lattice polygons[END_REF]. In contrast, n 2 points in convex (hence general) position trivially determine 2 n 2 -1 convex polygons. Erdős [START_REF] Erdős | Some more problems on elementary geometry[END_REF] proved that the minimum number of convex polygons determined by n points in general position is exp(Θ(log 2 n)). Determining (or estimating) the minimum number of convex polygons in an n × n Cartesian product and in higher dimensions remain as open problems.

Our motivating problem was the reconstruction of a convex polygon from the x-and y-projections of its vertices. We presented a 1 2 -approximation for computing the maximal size of a convex polygon supported by a grid X × Y . Finding an efficient algorithm for the original problem, or proving its hardness, remains open. As our dynamic program does not directly extend to d ≥ 3, approximation algorithms in higher dimensions are also of interest.

Figure 1 :

 1 Figure 1: Maximum-size supported convex polygons of respective sizes 3, 4, 4, and 5 in n × n grids, where n is between 3 and 6.

Lemma 2 .Lemma 3 .

 23 (Payne and Wood [22]) Every set of N points in the plane with at most collinear, ≤ O( √ N ), contains a set of Ω( N/ log ) points in general position. Every n × n grid supports a convex polygon of size (1 -o(1)) log n.

Figure 4 :

 4 Figure 4: A sequence X of 17 elements and nested intervals [a 0 , b 0 ] ⊃ . . . ⊃ [a 4 , b 4 ].

Corollary 7 .

 7 Every set of n real numbers contains an MD subset of size (log n)/2 + 1. For every n ∈ N, there exist a set of n real numbers in which the size of every MD subset is at most log n + 1.Proof. Since every 2-MD set is MD, the lower bound follows from Lemma 6. The upper bound construction is the point set Y defined in the proof of Lemma 4, for which every chain in or supported by {0, . . . , n -1} × Y has at most log n + 1 vertices. Let {b 0 , . . . , b -1 } ⊂ Y be an MD subset such that b 0 < . . . < b -1 . Then {(i, b i ) : i = 0, . . . , -1} ⊂ X × Y is in or . Consequently, every MD subset of Y has at most log n + 1 terms, as claimed.

4 Figure 5 : A 7 ×

 457 Figure 5: A 7 × 7 grid {a 1 , . . . , a 7 } × {b 1 , . . . , b 7 }, where the differences between consecutive xcoordinates (resp., y-coordinates) decrease by factors of 2 or higher. The point sets {(0, 0)}∪{(a i , b j ) : i + j = k}, for k = 2, . . . , 8, form nested convex chains.

  r 1 .x = x i+n-k+1 . So for a fixed value of k, we need only consider O(|Y | 2 |X|) inputs for C(l, r). Moreover, the recursive calls in the last two cases need only consider O(|Y |) values of v. This implies that there are O(|Y | 3 |X|) possible inputs to C(l, r) over all k. As an entry now depends on O(|Y |) subproblems and each is evaluated in constant time, the corresponding values can be computed in O(|Y | 4 |X|) = O(n 5 ) time and O(n 4 ) space. Similarly, we can test whether there is a cap of size n in within the same time and space bounds.

1 2 -

 2 approximation for the maximum supported convex polygon in O(n 6 ) time and O(n 2 ) space. The same strategy provides an1 2 -approximation for the maximum supported polygon in , , , and in in O(n 4 ) time and O(n 2 ) space using[START_REF] Edelsbrunner | Topologically sweeping an arrangement[END_REF] Thm. 5.1.2].

Figure 7 :

 7 Figure 7: Encoding the grid lines.

Figure 8 :

 8 Figure 8: The n × n grid defined in Section 4.2, with n = 9 = 2m + 3 for m = 3, before doubling the median lines. The segments (parts of grid lines) incident to vertices are drawn in bold.

  its internal angles are strictly smaller than π. A point set in R 2 is in convex position if it is the vertex set of a convex polygon; and it is in general position if no three points are collinear. Similarly, a polyhedron P in R d is convex if it is the convex hull of a finite set of points. A point set in R d is in convex position if it is the vertex set of a convex polytope; and it is in general position if no d + 1 points lie on a hyperplane. In R d , we say that the x d -axis is vertical, hyperplanes orthogonal to x d are horizontal, and understand the above-below relationship with respect to the x d -axis. Let e d be a standard basis vector parallel to the x d -axis. A point set P in R d is full-dimensional if no hyperplane contains P .

  1 ,

	Figure 2: An 8 × 8 grid without convex chains of size greater than 4 = log 8 + 1. X = {0, 1, . . . , 7},
	Y = {0, 1, 16, 17, 256, 257, 272, 273}. Two lines through pairs of grid points are drawn in blue.
	slope(p, p )

All logarithms in this paper are of base

each quadrant of the grid (excluding the extreme vertices). The convexity follows from our earlier observations. The total number of such polygons is

The first step uses the following estimate, which can be derived from Stirling's formula for the factorial [START_REF] Dumitrescu | Bounds on the maximum multiplicity of some common geometric graphs[END_REF]. Let 0 < α < 1, then

For the lower bound on G(n), the only difference is that we now allow grid lines to contain vertices in two chains. We obtain a maximum when we divide the grid lines evenly between the three groups (bottom chain, top chain, both chains). Thus, we select m/3 vertical grid lines left of the median to participate in the bottom chain, another m/3 to participate in the top chain and the remaining m/3 participate in both. We repeat this selection to the right of the median and on both sides of the median horizontal line. As before, this results in a convex polygon with the same number of vertices in each quadrant of the grid-exactly 2m/3 this time. The number of such polygons is

To translate these bounds to bounds on F (n) and F (n), where some grid lines may contain no vertices of the polygon, we observe that the arguments for the bounds above also work for a subgrid of X × Y , provided that the subgrid includes the boundary and medians and has the same number of grid lines on each side of the median in both directions. For F (n), we select 2m/3 grid lines on each side of each median (balancing no vertices with the two different chains) to make up our subgrid and plug in the bound on Ḡ(n), which yields

Finally, for the bound on F (n), we select 3m/4 grid lines on each side of each median (balancing no vertices with the three different options for a grid line in the proof of G(n)), to make up our subgrid and plug in the bound on G(n), giving

The maximum number of weakly convex polygons

Let W (n) denote the maximum number of weakly convex polygons that contained in an n × n grid. A polygon P in R 2 is weakly convex if all of its internal angles are less than or equal to π. Since W (n) ≥ F (n), we have W (n) = Ω * (16 n ). In fact, a slightly better lower bound trivially holds even for the n × n section of the integer lattice Z 0 = [n] × [n]. Consider all polygons whose vertices are


K Srujay Varma

Shaik Riyaaz Uddien

G Narendar

V Durga

Shaik Riyaaz Uddien

V Durga Prasad

Grey Relational Analysis for Wire-EDMed HCHCr using Taguchi's Technique 1

Keywords: HCHCr, copper electrode, wire EDM, Taguchi's and grey relational analysis

HAL is

Introduction.

HCHCr stands for High Carbon High Chromium steel comes under one of the three series of cold work group, which has many applications in low temperature cutting and forming processes. Mainly used as punches, dies, rolling dies, finishing rolls for tyre mills etc., This material was chosen as area of interest because it has low machinability comparing to other steels [START_REF] Ugrasen | Optimization of Process Parameters in Wire EDM of HCHCr Material Using Taguchi's Technique[END_REF], [START_REF]Comparison of HCHCr Steel and Carbide Punch and Die Increase its Strength and Life by Tin & Ceramics coating[END_REF], [START_REF] Naik | Charactarization and Surface Roughness Study Of Hchcr Material To Prepare Precision Stamping Punch[END_REF], [START_REF] Verhoeven | Steel Metallurgy for the Non-Metallurgist[END_REF]. Wire-Electrical Discharge Machining (wEDM) is an extension of the die-sink EDM which has capability to cut complicated shapes on tough metals with excellent surface finish and low residual stresses [START_REF] Dongre | Multi-objective optimization for silicon wafer slicing using wire-EDM process[END_REF], [START_REF] Zakaria | Effect of Wire EDM Cutting Parameters for Evaluating of Additive Manufacturing Hybrid Metal Material[END_REF]. It advantages includes less processing time and less tool cost. A conductive material acts as a wire electrode and work piece gets eroded by series of discrete sparks between the work piece and wire electrode separated by a thin film of dielectric fluid. Dielectric fluid flashes away the eroded material and it also acts as a coolant. Because of its less cutting forces, its applications has been extended to machine metal foams used in heat exchangers and slicing silicon wafers used in solar cells and microelectronic components. An important aspect while machining using wire-EDM is the selection of electrode material. There are various conductive materials that can be used as electrodes but the more frequently used electrode material is copper. So copper was chosen as electrode in this study [START_REF] Rao | Effect of wire EDM conditions on generation of residual stresses in machining of aluminum 2014 T6 alloy[END_REF], [START_REF] Khajornrungruang | Analysis of Effects of Cutting Parameters of Wire Electrical Discharge Machining on Material Removal Rate and Surface Integrity[END_REF]. Taguchi method based on orthogonal array was used for designing experiments in MINITAB 17 Software [START_REF] Tilekar | Process Parameter Optimization of Wire EDM on Aluminum and Mild Steel by Using Taguchi Method[END_REF], [START_REF] Durairaj | Analysis of process parameters in wire EDM with stainless steel using single objective Taguchi method and multi objective grey relational grade[END_REF] and Grey Relational Analysis was conducted to find out the optimized input parameters for obtaining best output responses [START_REF] Durairaj | Optimization of Inconel 600 Alloy Micro Turning Process Using Grey Relational Analysis[END_REF], [START_REF] Xxx | Development of a Thermo-Physical Model for Multispark Wire EDM Process[END_REF].

Experimental method. The workpiece material, electrode wire and machine used to carry out the experiments are described below. Design factors and response variable as well as methodology implemented for the experimentation is also outlined.

Material and Equipment used

The wire EDM used to carry out the experiments was Wire EDM CNC Sprint Cut 734 (Electranica Sprint Cut 734) from Electrionica Ltd, Pune as shown in Fig 1 . Dielectric fluid used in this machine is de-ionised water and copper wire of diameter 0.25 mm is taken as electrode material. HCHCr steel substrates of dimension 100 x 50 x 10 mm were considered for machining. Vickers Hardness Tester with diamond indenter and Surface-SJ 301 surface roughness tester made by Mitutoyo Company were used.

Experimental Design

Taguchi method based on orthogonal array was used to design experiments in this study. The process parameters were selected depending upon machine, cutting tool and work piece capability. The input process parameters taken in this experiment are pulse-on time (Ton), pulse-off time (Ton), current (Ip) and servo voltage (SV) as shown in Table 1.

Experimental Procedure

The number of experiments was limited to 9 according to L9 orthogonal array using Taguchi's statistical technique. The experiments were carried out by varying process parameters at three levels. After conducting experiments, the substrates were taken out, dried and measured for Material Removal Rate (mm 3 /min), Hardness (HV) and Surface Roughness (µm) were measured. Material Removal Rate (MRR) was calculated using the formula in equation [START_REF] Ugrasen | Optimization of Process Parameters in Wire EDM of HCHCr Material Using Taguchi's Technique[END_REF].

MRR = VR/TM (1)
where VRvolume of material removed after machining;

TMmachining time. The surface roughness tester is used to measure the roughness on the work piece after machining. This observation helped in finding how the experiment conditions are affecting the surface roughness. Then hardness of the surface was tested using micro hardness tester having Vickers diamond indenter and indenter is pressed into the materials surface with a penetrator and a weight of 1000 gms. The result of applying the load with a penetrator is an indent or permanent deformation of material surface caused by the shape of the indentor. The values obtained for MRR, Surface Roughness and Hardness are shown in Table 2.

Results and discussions:

Grey Relational Analysis was performed on the data obtained from experiments.

Grey Relational Analysis

In grey relational analysis first normalized data for the responses should be generated considering the lower the better and higher the better criterion this process is known as Grey relational generation.

There are four steps for performing grey relational analysis as shown in stepwise.

1) MRR and Hardness should follow the higher the better criterion, which can be expressed as

xi (k) = [yi (k) -min yi (k)] /[max yi (k) -min yi (k)] ( 2
)
Surface Roughness follow the lower the better criterion, which can be expressed as

xi (k) = [max yi (k) -yi (k) ] / [max yi (k) -min yi (k)] (3)
Normalized data of responses after step 1 is shown in table 3.

Here x0 (k) = 1, let delta = difference of absolute value.

The values obtained after step 2 is deviation sequence is shown in table 4.

3) The Grey Relational Coefficient ξi (k) can be calculated as

ξi (k) = [∆min + ψ ∆max] / [∆0i (k) + ψ ∆max] (5)
. After averaging the grey relational coefficients, the grey relational grade γi can be computed as:

γi = 1/n ∑ n k=1 ξi (k)
Let Grey Relational Grade be represented as GRG. It is observed from the GRC and GRG table that rank 1 was obtained for experiment 1, which represents the parameters chosen for experiment 1 gives better results combining all three-output responses.

Summary. The number of experiments to be conducted was reduced following L9 orthogonal array of Taguchi Method which in turn reduced experimental cost and time. The best combination of obtaining optimized output was found using Grey Relational Analysis. It was found as TON = 100, TOFF = 55, IP = 10 and SV = 10, which are the parameters used for conducting experiment 1.

Table 1 .

 1 Input process parameters of Wired EDM.

	S.NO.	Process Parameters	Level 1 Level 2 Level 3
	1	Pulse-on Time (Ton)	100	105	110
	2	Pulse-off Time (Toff)	55	59	63
	3	Peak Current (Ip)	10	11	12
	4	Servo Voltage (Sv)	10	55	90

Table 2 .

 2 Experimental readings.

			Actual values	MRR	Hardness	Surface Roughness
	Exp No	Ton	Toff Ip SV (mm 3 /min) HV	µm
	1	100 55	10 10 0.0658	33	2.695
	2	100 59	11 55 0.1976	34	3.497
	3	100 63	12 90 0.2045	32	3.855
	4	105 55	11 90 0.2272	34	3.8
	5	105 59	12 10 0.0946	33	2.8
	6	105 63	10 55 0.3073	34	3.32
	7	110 55	12 55 0.3246	34	3.45
	8	110 59	10 90 0.3719	34	3.82
	9	110 63	11 10 0.1515	29	3.82

Table 3 .

 3 Normalized data of responses.

	S.NO	MRR (x1),	Surface Roughness (x2),	Hardness (x3), (HRC)
		(mm 3 /min)	(Ra)
	1	0	1	0.8
	2	0.4305	0.3086	1
	3	0.4531	0	0.6
	4	0.5272	0.0474	1
	5	0.0940	0.9094	0.8
	6	0.7889	0.4612	1
	7	0.8454	0.3491	1
	8	1	0.0301	1
	9	0.2799	0.0301	0
	2) Let the normalized data of MRR may be represented with k=1, that of surface roughness with k=2
	and that of hardness with k=3

Table 4 .

 4 Deviation sequence.

	S.NO MRR (x1), (mm 3 /min) Surface Roughness (x2), (Ra) Hardness (x3), (HRC)
	1	1	0	0.2
	2	0.5695	0.6914	0
	3	0.5469	1	0.4
	4	0.4728	0.9526	0
	5	0.906	0.0906	0.2
	6	0.2111	0.5388	0
	7	0.1546	0.6509	0
	8	0	0.9699	0
	9	0.7201	0.9699

Table 5 .

 5 Grey Relational Coefficient.

	S.NO	MRR (mm 3 /min)	SR (Ra)	Hardness (HRC)
	1	0.3333	1	0.7142
	2	0.4675	0.4196	1
	3	0.4776	0.3333	0.555
	4	0.5139	0.3442	1
	5	0.3556	0.8471	0.7142
	6	0.7031	0.4813	1
	7	0.7638	0.4344	1
	8	1	0.3401	1
	9	0.4098	0.3401	0.333
	Let GRC = Grey Relational Coefficient

Table 6 .

 6 GRC and GRG table.

	S.NO	MRR (mm 3 /min)	SR (Ra)	Hardness	GRG Rank
		GRC1	GRC2	(HRC) GRC3
	1	0.3333	1	0.7142	0.6825 1
	2	0.4004	0.7098	0.8571	0.6577 3
	3	0.4261	0.5843	0.7564	0.5889 9
	4	0.4480	0.5242	0.8173	0.5965 8
	5	0.4295	0.5888	0.79668	0.6049 7
	6	0.4751	0.5709	0.8305	0.6255 5
	7	0.5164	0.5514	0.8547	0.6408 4
	8	0.5768	0.525	0.8729	0.6582 2
	9	0.5582	0.5044	0.8129	0.6251 6

© 2017 The Authors. Published by Magnolithe GmbH. This is an open access article under the CC BY-NC-ND license http://creativecommons.org/licenses/by-nc-nd/4.0/

Acknowledgement:

I would like to specially thank Prof. G. Narendar, Osmania University, Hyderabad and Prof. V. Durga Prasad, SRKR Engineering College, Andhra Pradesh for spending your valuable time to guide me during my project.