Let S be a set of 2n points on a circle such that for each point p 2 S also its antipodal (mirrored with respect to the circle center) point p 0 belongs to S. A polygon P of size n is called antipodal if it consists of precisely one point of each antipodal pair (p;p 0 ) of S. We provide a complete characterization of antipodal polygons which maximize (minimize, respectively) the area among all antipodal polygons ofS. Based on this characterization, a simple linear time algorithm is presented for computing extremal antipodal polygons. Moreover, for the generalization of antipodal polygons to higher dimensions we show that a similar characterization does not exist.
ph Extremal problems: Plane geometry is rich of extremal problems, often dating back till the ancient Greeks. During the centuries many of these problems have been solved by geometrical reasoning. Specifically, extremal problems on convex polygons have attracted the attention of both fields, geometry and optimization. In computational geometry, efficient algorithms have been proposed for computing extremal polygons w.r.t. several different properties @cite_3 . In operations research, global optimization techniques have been extensively studied to find convex polygons maximizing a given parameter @cite_12 . A geometric extremal problem similar to the one studied in this paper was solved by Fejes T ' o th @cite_10 almost fifty years ago. He showed that the sum of pairwise distances determined by @math points contained in a circle is maximized when the points are the vertices of a regular @math -gon inscribed in the circle. Recently, the discrete version of this problem has been reviewed in @cite_7 and problems considering maximal area instead of the sum of inter-point distances have been solved in @cite_2 .
@cite_7 @cite_3 @cite_2 @cite_10 @cite_12
2002285779 2048802156 2093480133 2045156582
Consider a convex polygon V n with n sides, perimeter P n , diameter D n , area A n , sum of distances between vertices S n and width W n . Minimizing or maximizing any of these quantities while fixing another defines 10 pairs of extremal polygon problems (one of which usually has a trivial solution or no solution at all). We survey research on these problems, which uses geometrical reasoning increasingly complemented by global optimization methods. Numerous open problems are mentioned, as well as series of test problems for global optimization and non-linear programming codes. This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross-section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed. Extremal Combinatorics is one of the central areas in Discrete Mathematics. It deals with problems that are often motivated by questions arising in other areas, including Theoretical Computer Science, Geometry and Game Theory. This paper contains a collection of problems and results in the area, including solutions or partial solutions to open problems suggested by various researchers. The topics considered here include questions in Extremal Graph Theory, Polyhedral Combinatorics and Probabilistic Combinatorics. This is not meant to be a comprehensive survey of the area, it is merely a collection of various extremal problems, which are hopefully interesting. The choice of the problems is inevitably biased, and as the title of the paper suggests, it is a sequel to a previous paper [N. Alon, Problems and results in extremal combinatorics-I, Discrete Math. 273 (2003), 31-53.] of the same flavor, and hopefully a predecessor of another related future paper. Each section of this paper is essentially self contained, and can be read separately. Abstract Given a set S of n points in the plane and a convex polygon P with m vertices, we consider the problem of finding a translation of P that contains the maximum number of points in S . We present two different solutions. Our first algorithm uses standard line-sweep techniques and requires O( nk log( nm ) + m ) time where k is the maximum number of points contained. Our second algorithm requires O( nk log( mk ) + m ) time, which is the asymptotically fastest known algorithm for this problem. Both algorithms require optimal O( m + n ) space. The algorithms also solve in the same running time the bichromatic variant of the problem, where we are given two point sets A and B and the goal is to maximize the number of points covered from A while minimizing the number of points covered from B .