期刊
DISCRETE MATHEMATICS
卷 344, 期 10, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.disc.2021.112541
关键词
Discrete geometry; Point set; Circle containment; Voronoi diagram
类别
资金
- Spanish Ministry of Science, Innovation and Universities [PRE2018-085668, TIN2016-80622-P]
- [DGR 2017SGR1640]
- [MTM2015-63791-R]
- [PID2019-104129GB-I00]
- [DGR 2017SGR1336]
This study proves the specific properties of red and blue point sets on the plane, using higher order Voronoi diagrams. It also investigates the number of collinear edges in higher order Voronoi diagrams and provides specific constructions.
We prove that every set of n red and n blue points in the plane contains a red and a blue point such that every circle through them encloses at least n(1 - 1/root 2) - o(n) points of the set. This is a two-colored version of a problem posed by Neumann-Lara and Urrutia. We also show that every set S of n points contains two points such that every circle passing through them encloses at most left perpendicular2n-1/3right perpendicular points of S. The proofs make use of properties of higher order Voronoi diagrams, in the spirit of the work of Edelsbrunner, Hasan, Seidel and Shen on this topic. Closely related, we also study the number of collinear edges in higher order Voronoi diagrams and present several constructions. (C) 2021 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据