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
2116417064 2052562833 2006554643 2108509297 2002285779
Many problems concerning the theory and technology of rhythm, melody, and voice-leading are fundamentally geometric in nature. It is therefore not surprising that the field of computational geometry can contribute greatly to these problems. The interaction between computational geometry and music yields new insights into the theories of rhythm, melody, and voice-leading, as well as new problems for research in several areas, ranging from mathematics and computer science to music theory, music perception, and musicology. Recent results on the geometric and computational aspects of rhythm, melody, and voice-leading are reviewed, connections to established areas of computer science, mathematics, statistics, computational biology, and crystallography are pointed out, and new open problems are proposed. Given n points in the plane, we present algorithms for finding maximum perimeter or area convex k-gons with vertices k of the given n points. Our algorithms work in linear space and time @math . For the special case @math we give @math algorithms for these problems. Several related issues are discussed. A musical scale can be viewed as a subset of notes or pitches taken from a chromatic universe. For the purposes of this paper we consider a chromatic universe of twelve equally spaced pitches. Given integers (N,K) with N > K we use particular integer partitions of N into K parts to construct distinguished sets, or scales. We show that a natural geometric realization of these sets have maximal area, so we call them maximal area sets. We then discuss properties of maximal area sets for the integer pairs (12,5) (12,6) (12,7) and (12,8) with the obvious relevance to scales in our normal chromatic collection of 12 pitches. Complementary maximal area sets are those sets where the chosen K notes realize maximal area, and the complementary N − K notes also realize maximal area. The complementary maximal area sets closely match a significant collection of scales identified in a book on jazz theory by Mark Levine(The jazz theory book. Sher Music Co., Pet aluma, 1995). where d denotes the diameter of the circumcircle of the points. The constant cannot be replaced by a greater one. In order to prove our theorem we denote the points by P . . . . ,P ,Fixing the points . . . . , P,,, we consider S,, as a function of the point P . Since the distances P P., , . . . , P1P, are convex functions of P , the same can b e 'stated of S,i. It follows that S, takes its maximum for a point P1 ly!ng on the boundary C of the circumcircle of the points. Therefore all points may be supposed to lie on C. Furthermore we suppose that C is a unit circle and that the cyclical order of the points is PI . . . . . P,,,. Introducing the notations P,+I = P1, . . . , P , 1 P,,- we consider the sum 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.