如何排除一条线'segregating'一组点的存在
how to exclude the existence of a line 'segregating' a set of points
为模糊的标题道歉：我找不到我正在寻找的理论的合适名称（这就是我问这个问题的原因），所以我将用一个例子来解释它，我希望有人能给我指出正确的方向。
假设您有一组二维点。
以下 R 代码：
# make a random set of N points in 2D space as a numerical matrix
set.seed(1010)
d = 2
N = 15
ps <- matrix(rnorm(d*N), , d)
# center the points (subtract the mean of each coordinate)
pss <- scale(ps,scale=F)
# represent the points in a 2D plot, with the origin (the new mean) in red
plot(pss)
text(pss,label=1:N,pos=4)
points(0,0,col=2,pch=16)
text(0,0,label=0)
abline(v=0)
abline(h=0)
应该制作这样的情节：
考虑第 7 点。凭直觉可以看出，有几条可能的线穿过第 7 点，'leave' 线上 'one side' 上的所有其他点（即 'segregate' 它们在 half-plane 定义的行中。
考虑第 6 点。永远不会有任何一条线通过第 6 点，其中一个 half-plane 包含所有点。
像9这样的点也可以有这样一条线，虽然从图中看不是特别明显。
问题: 有没有办法排除每个特定点都存在这样一条线？意思是，是否可以对点的坐标进行一些操作，证明对于给定点，这样的线可以 NOT 存在（因此可以快速将该点分类为可以和/或可以有它）？我也在考虑更高维度的应用，线就是平面等等
到目前为止，我对该主题的所有搜索都让我想到了 'convex hull' 和 'boundary' 等概念，它们看起来确实与我正在寻找的内容密切相关，但远远超出了我的要求对点进行分类的简单要求，并报告为'output-sensitive'，确实因为它们提供了很多关于船体本身的信息，我不需要这些信息。
有什么想法吗？
谢谢！
给定一组点，以下关于单个点 p 的两个陈述是等价的：
- 有一条线通过 p 使得集合中的每个点都位于线的同一侧（或线上），
- p 在集合的 convex hull.
的边界上
这是真的，因为如果p在凸包的内部，那么通过p的任何一条线都会把凸包分成两部分。如果线的一侧在集合中没有点，则另一侧是包含所有点的较小凸区域。这将与凸包的定义相矛盾，凸包是包含每个点的最小凸集。
所以满足 属性 关于有一条线不将集合一分为二的点集，恰好是凸包边界上的同一组点。后者是什么凸包算法returns，所以从逻辑上讲，任何解决集合中每个点问题的算法都是凸包算法。
我能想到的唯一细微差别是，标准凸包算法通常也会 return 以特定顺序排列边界点，而您不需要以任何特定顺序排列它们。但我认为当顺序无关紧要时，没有更有效的凸包算法。 运行 时间在最坏的情况下是 O(n log n)，这给你每个点的平均查询时间最多为 O(log n)。
如果你想测试集合中的每个点，这对于这个问题来说是渐进最优的，因为根据 an arXiv paper by Herman Haverkort. There's evidence that this is optimal even for just finding the cardinality of the convex hull (see this paper by Davis Avis).
为模糊的标题道歉：我找不到我正在寻找的理论的合适名称（这就是我问这个问题的原因），所以我将用一个例子来解释它，我希望有人能给我指出正确的方向。
假设您有一组二维点。
以下 R 代码：
# make a random set of N points in 2D space as a numerical matrix
set.seed(1010)
d = 2
N = 15
ps <- matrix(rnorm(d*N), , d)
# center the points (subtract the mean of each coordinate)
pss <- scale(ps,scale=F)
# represent the points in a 2D plot, with the origin (the new mean) in red
plot(pss)
text(pss,label=1:N,pos=4)
points(0,0,col=2,pch=16)
text(0,0,label=0)
abline(v=0)
abline(h=0)
应该制作这样的情节：
考虑第 7 点。凭直觉可以看出，有几条可能的线穿过第 7 点，'leave' 线上 'one side' 上的所有其他点（即 'segregate' 它们在 half-plane 定义的行中。
考虑第 6 点。永远不会有任何一条线通过第 6 点，其中一个 half-plane 包含所有点。
像9这样的点也可以有这样一条线，虽然从图中看不是特别明显。
问题: 有没有办法排除每个特定点都存在这样一条线？意思是，是否可以对点的坐标进行一些操作，证明对于给定点，这样的线可以 NOT 存在（因此可以快速将该点分类为可以和/或可以有它）？我也在考虑更高维度的应用，线就是平面等等
到目前为止，我对该主题的所有搜索都让我想到了 'convex hull' 和 'boundary' 等概念，它们看起来确实与我正在寻找的内容密切相关，但远远超出了我的要求对点进行分类的简单要求，并报告为'output-sensitive'，确实因为它们提供了很多关于船体本身的信息，我不需要这些信息。
有什么想法吗？
谢谢！
给定一组点，以下关于单个点 p 的两个陈述是等价的：
- 有一条线通过 p 使得集合中的每个点都位于线的同一侧（或线上），
- p 在集合的 convex hull. 的边界上
这是真的，因为如果p在凸包的内部，那么通过p的任何一条线都会把凸包分成两部分。如果线的一侧在集合中没有点，则另一侧是包含所有点的较小凸区域。这将与凸包的定义相矛盾，凸包是包含每个点的最小凸集。
所以满足 属性 关于有一条线不将集合一分为二的点集，恰好是凸包边界上的同一组点。后者是什么凸包算法returns，所以从逻辑上讲，任何解决集合中每个点问题的算法都是凸包算法。
我能想到的唯一细微差别是，标准凸包算法通常也会 return 以特定顺序排列边界点，而您不需要以任何特定顺序排列它们。但我认为当顺序无关紧要时，没有更有效的凸包算法。 运行 时间在最坏的情况下是 O(n log n)，这给你每个点的平均查询时间最多为 O(log n)。
如果你想测试集合中的每个点，这对于这个问题来说是渐进最优的，因为根据 an arXiv paper by Herman Haverkort. There's evidence that this is optimal even for just finding the cardinality of the convex hull (see this paper by Davis Avis).