More Like this

1. Maximal Distortion of Geodesic Diameters in Polygonal Domains

   https://doi.org/10.1007/978-3-031-34347-6_17  

   Adrian Dumitrescu; Csaba D. Tóth (June 2023, Combinatorial Algorithms (IWOCA 2023))

   For a polygon P with holes in the plane, we denote by ϱ(P) the ratio between the geodesic and the Euclidean diameters of P. It is shown that over all convex polygons with h convex holes, the supremum of ϱ(P) is between Ω(h1/3) and O(h1/2) . The upper bound improves to O(1+min{h3/4Δ,h1/2Δ1/2}) if every hole has diameter at most Δ⋅diam2(P) ; and to O(1) if every hole is a fat convex polygon. Furthermore, we show that the function g(h)=supPϱ(P) over convex polygons with h convex holes has the same growth rate as an analogous quantity over geometric triangulations with h vertices when h→∞ . 

   more » « less
2. The pentagram map, Poncelet polygons, and commuting difference operators

   https://doi.org/10.1112/S0010437X22007345  

   Izosimov, Anton (May 2022, Compositio Mathematica)

   The pentagram map takes a planar polygon $$P$$ to a polygon $P'$ whose vertices are the intersection points of consecutive shortest diagonals of $$P$$ . This map is known to interact nicely with Poncelet polygons, that is, polygons which are simultaneously inscribed in a conic and circumscribed about a conic. A theorem of Schwartz states that if $$P$$ is a Poncelet polygon, then the image of $$P$$ under the pentagram map is projectively equivalent to $$P$$ . In the present paper, we show that in the convex case this property characterizes Poncelet polygons: if a convex polygon is projectively equivalent to its pentagram image, then it is Poncelet. The proof is based on the theory of commuting difference operators, as well as on properties of real elliptic curves and theta functions. 

   more » « less
3. Balanced centroidal power diagrams for redistricting

   https://doi.org/10.1145/3274895.3274979  

   Cohen-Addad, Vincent; Klein, Philip N.; Young, Neal E. (November 2018, Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems)

   We consider the problem of political redistricting: given the locations of people in a geographical area (e.g. a US state), the goal is to decompose the area into subareas, called districts, so that the populations of the districts are as close as possible and the districts are ``compact'' and ``contiguous,'' to use the terms referred to in most US state constitutions and/or US Supreme Court rulings. We study a method that outputs a solution in which each district is the intersection of a convex polygon with the geographical area. The average number of sides per polygon is less than six. The polygons tend to be quite compact. Every two districts differ in population by at most one (so we call the solution balanced). In fact, the solution is a centroidal power diagram: each polygon has an associated center in ℝ³ such that * the projection of the center onto the plane z = 0 is the centroid of the locations of people assigned to the polygon, and * for each person assigned to that polygon, the polygon's center is closest among all centers. The polygons are convex because they are the intersections of 3D Voronoi cells with the plane. The solution is, in a well-defined sense, a locally optimal solution to the problem of choosing centers in the plane and choosing an assignment of people to those 2-d centers so as to minimize the sum of squared distances subject to the assignment being balanced. * A practical problem with this approach is that, in real-world redistricting, exact locations of people are unknown. Instead, the input consists of polygons (census blocks) and associated populations. A real redistricting must not split census blocks. We therefore propose a second phase that perturbs the solution slightly so it does not split census blocks. In our experiments, the second phase achieves this while preserving perfect population balance. The district polygons are no longer convex at the fine scale because their boundaries must follow the boundaries of census blocks, but at a coarse scale they preserve the shape of the original polygons. 

   more » « less
4. Semiclassical resolvent bounds for short range L ∞ potentials with singularities at the origin

   https://doi.org/10.3233/ASY-231872  

   Shapiro, Jacob (February 2024, Asymptotic Analysis)

   We consider, for h , E > 0, resolvent estimates for the semiclassical Schrödinger operator − h 2 Δ + V − E. Near infinity, the potential takes the form V = V L + V S , where V L is a long range potential which is Lipschitz with respect to the radial variable, while V S = O ( | x | − 1 ( log | x | ) − ρ ) for some ρ > 1. Near the origin, | V | may behave like | x | − β , provided 0 ⩽ β < 2 ( 3 − 1 ). We find that, for any ρ ˜ > 1, there are C , h 0 > 0 such that we have a resolvent bound of the form exp ( C h − 2 ( log ( h − 1 ) ) 1 + ρ ˜ ) for all h ∈ ( 0 , h 0 ]. The h-dependence of the bound improves if V S decays at a faster rate toward infinity. 

   more » « less
5. Universal Geometric Graphs

   https://doi.org/10.1007/978-3-030-60440-0_14  

   Frati, Fabrizio; Hoffmann, Michael; Toth, Csaba D. (October 2020, Graph-Theoretic Concepts in Computer Science (WG 2020))

   null (Ed.)

   We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an n-vertex graph with O(nlogn) edges that contains every n-vertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0 , every n-vertex convex geometric graph that is universal for the class of the n-vertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex caterpillars. 

   more » « less