BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We say that a polygon inscribed in the circle is asymmetric if it contains no two antipodal points being the endpoints of a diameter. Given n diameters of a circle and a positive integer k<n, this paper addresses the problem of computing a maximum area asymmetric k-gon having as vertices k<n endpoints of the given diameters. The study of this type of polygons is motivated by ethnomusiciological applications.
Let S be a set of 2n points on a circle such that for each point p∈S also its antipodal (mirrored with respect to the circle center) point p′ belongs to S. A polygon P of size n is called \emph{antipodal} if it consists of precisely one point of each antipodal pair (p,p′) of S. We provide a complete characterization of antipodal polygons which maximize (minimize, respectively) the area among all antipodal polygons of S. 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.
Let S be a 2-colored (red and blue) set of n points in the plane. A subset I of S is an island if there exits a convex set C such that I=C∩S. The discrepancy of an island is the absolute value of the number of red minus the number of blue points it contains. A convex partition of S is a partition of S into islands with pairwise disjoint convex hulls. The discrepancy of a convex partition is the discrepancy of its island of minimum discrepancy. The coarseness of S is the discrepancy of the convex partition of S with maximum discrepancy. This concept was recently defined by Bereg et al. [CGTA 2013]. In this paper we study the following problem: Given a set S of n points in general position in the plane, how to color each of them (red or blue) such that the resulting 2-colored point set has small coarseness? We prove that every n-point set S can be colored such that its coarseness is O(n1/4logn). This bound is almost tight since there exist n-point sets such that every 2-coloring gives coarseness at least Ω(n1/4). Additionally, we show that there exists an approximation algorithm for computing the coarseness of a 2-colored point set, whose ratio is between 1/128 and 1/64, solving an open problem posted by Bereg et al. [CGTA 2013]. All our results consider k-separable islands of S, for some k, which are those resulting from intersecting S with at most k halfplanes.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.