Convexly independent subsets of Minkowski sums of convex polygons

被引：0
|
作者：
Skomra, Mateusz [1 ]
Thomasse, Stephan [2 ,3 ]
机构：
[1] Univ Toulouse, CNRS, LAAS CNRS, Toulouse, France
[2] Univ Lyon, EnsL, UCBL, CNRS,LIP, F-69342 Lyon 07, France
[3] Inst Univ France, Paris, France
来源：
DISCRETE MATHEMATICS | 2021年 / 344卷 / 08期
关键词：
Minkowski sum; Convex embeddings of graphs; Convexly independent sets; UNIT DISTANCES;
D O I：
10.1016/j.disc.2021.112472
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that there exist convex n-gons P and Q such that the largest convex polygon in the Minkowski sum P+Q has size Theta(n log n). This matches an upper bound of Tiwary. (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页数：7
相关论文
共 50 条
  • [1] Large convexly independent subsets of Minkowski sums
    Swanepoel, Konrad J.
    Valtr, Pavel
    ELECTRONIC JOURNAL OF COMBINATORICS, 2010, 17 (01):
  • [2] On the largest convex subsets in Minkowski sums
    Tiwary, Hans Raj
    INFORMATION PROCESSING LETTERS, 2014, 114 (08) : 405 - 407
  • [3] Convexly independent subsets of the Minkowski sum of planar point sets
    Eisenbrand, Friedrich
    Pach, Janos
    Rothvoss, Thomas
    Sopher, Nir B.
    ELECTRONIC JOURNAL OF COMBINATORICS, 2008, 15 (01):
  • [4] Exact Minkowski Sums of Polygons With Holes
    Baram, Alon
    Fogel, Efi
    Halperin, Dan
    Hemmer, Michael
    Morr, Sebastian
    ALGORITHMS - ESA 2015, 2015, 9294 : 71 - 82
  • [5] Exact Minkowski sums of polygons with holes
    Baram, Alon
    Fogel, Efi
    Halperin, Dan
    Hemmer, Michael
    Morr, Sebastian
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2018, 73 : 46 - 56
  • [6] Minkowski decomposition of convex lattice polygons
    Emiris, Ioannis Z.
    Tsigaridas, Elias P.
    ALGEBRAIC GEOMETRY AND GEOMETRIC MODELING, 2006, : 217 - +
  • [7] Minkowski sums of monotone and general simple polygons
    Oks, E
    Sharir, M
    DISCRETE & COMPUTATIONAL GEOMETRY, 2006, 35 (02) : 223 - 240
  • [8] Minkowski Sums of Monotone and General Simple Polygons
    Eduard Oks
    Micha Sharir
    Discrete & Computational Geometry, 2006, 35 : 223 - 240
  • [9] Minkowski sums of projections of convex bodies
    Goodey, P
    MATHEMATIKA, 1998, 45 (90) : 253 - 268
  • [10] Minkowski Sums of Rotating Convex Polyhedra
    Lien, Jyh-Ming
    PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SGG'08), 2008, : 228 - 229
12345