Algebraic k-Sets and Generally Neighborly Embeddings
Algebraic k-Sets and Generally Neighborly Embeddings
复制标题
代数 k 集和广义邻域嵌入
DOI：
10.1007/s00454-021-00340-1
复制
发表时间：
2022
影响因子：
0.8
通讯作者：
Rademacher, Luis
中科院分区：
文献类型：
--
作者：
Leroux, Brett;Rademacher, Luis
给定一组Sofn个点，ak-set是S的k个点的子集，可以通过超平面与其余点严格分开。类似地，我们可以考虑 k 个面，它是通过沙子的 d 个点的超平面，并且一侧有 k 个点。一个臭名昭著的开放问题是确定 k 集最大数量的渐近。在本文中，我们研究了用代数曲面代替超平面的 k-set/k-facet 问题的变体。与原始的 k-set/k-facet 问题形成鲜明对比的是，有一些代数曲线的自然族可以准确计算 k-facet 的数量。例如，我们证明平面上任意位置的点集的二分圆锥曲线的数量为 $$2\left( {\begin{array}{c}n+2\\ 2\end{array}}\right) ^2$$。为了理解我们的论点的局限性，我们研究了一类我们通常称为邻接嵌入的映射，它将通用点集映射到邻接位置。此外，我们给出了一个简单的论点，它改进了凸位置点集的 k 集/k 面数量的已知界限。
Given a setSofnpoints in, ak-set is a subset ofkpoints ofSthat can be strictly separated by a hyperplane from the remainingpoints. Similarly, one may considerk-facets, which are hyperplanes that pass throughdpoints ofSand havekpoints on one side. A notorious open problem is to determine the asymptotics of the maximum number ofk-sets. In this paper we study a variation on thek-set/k-facet problem with hyperplanes replaced by algebraic surfaces. In stark contrast to the originalk-set/k-facet problem, there are some natural families of algebraic curves for which the number ofk-facets can be counted exactly. For example, we show that the number of halving conic sections for any set ofpoints in general position in the plane is $$2\left( {\begin{array}{c}n+2\\ 2\end{array}}\right) ^2$$. To understand the limits of our argument we study a class of maps we callgenerally neighborly embeddings, which map generic point sets into neighborly position. Additionally, we give a simple argument which improves the best known bound on the number ofk-sets/k-facets for point sets in convex position.
登录
查看更多内容
通过凸伪圆进行分离
影响因子：
0.8
作者：
N. Chevallier;A. Fruchard;Dominique Schmitt;J. Spehner
通讯作者：
J. Spehner
影响因子：
0.8
作者：
M. Sharir;Shakhar Smorodinsky;G. Tardos
通讯作者：
G. Tardos
平面 k 集和相关问题的改进界限
影响因子：
0.8
作者：
T. Dey
通讯作者：
T. Dey
DOI：
10.1080/00029890.2004.11920117
发表时间：
2004
期刊：
The American Mathematical Monthly
影响因子：
--
作者：
Federico Ardila
通讯作者：
Federico Ardila
组合学、概率和计算 凸包的点选择和弱 E 网 凸包的点选择和弱 E 网
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
Noga Alon;I. Bárány;Z. Füredi;D. Kleitman;I. Bárány;Z. Furedi
通讯作者：
Z. Furedi