On the largest convex subsets in Minkowski sums

被引：4

作者：

Tiwary, Hans Raj ^{[1
,2
]}

机构：

[1] Charles Univ Prague, Dept Appl Math, KAM, CR-11800 Prague 1, Czech Republic

[2] Charles Univ Prague, Inst Theoret Comp Sci ITI, CR-11800 Prague 1, Czech Republic

来源：

INFORMATION PROCESSING LETTERS | 2014年 / 114卷 / 08期

关键词：

Minkowski sum; Combinatorics of planar point sets; Convex subsets; Combinatorial problems;

D O I：

10.1016/j.ipl.2014.02.013

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given two point sets A, B subset of R-2 of n points each, the Minkowski sum A + B has a quadratic number of points in general. How large can a subset S subset of A + B be if S is required to be convex? We prove that when A and B are both convex then S can have only O (n log n) points. This complements the existing results that are known when A and B are not in convex position or when B = A and A is convex. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：405 / 407

页数：3