高维点对称凸壳的点内外快速预检测算法需求

Hey there! Let's tackle this high-dimensional convex hull membership pre-check problem, especially focusing on the point-symmetric property you have—this is a key advantage we can leverage heavily to build a fast, effective pre-filter.

核心思路 #

Your point-symmetric convex hull has two critical properties we can exploit:

1. The origin is an interior point of the convex hull (since it's non-degenerate and symmetric).
2. For any direction vector ( u ), the maximum projection of the convex hull onto ( u ) equals the absolute value of the minimum projection (thanks to symmetry).

We'll combine these to build a three-way pre-check: definitely interior, definitely exterior, or unable to determine.

预处理（仅执行一次） #

These steps run once on your 10,000-point defining set ( S ):

1. Generate a direction set
   • Include all standard axis directions (( e_1, e_2, ..., e_d ))—since the hull is symmetric, we don't need negative axes.
   • Add 50-200 random unit vectors (or use low-discrepancy sequences like Halton for more uniform coverage) to capture off-axis directions.
2. Compute support function values
   • For each direction ( u ) in your set, calculate ( h_u = \max_{x \in S} u \cdot x ). Since ( S ) is symmetric, this is equivalent to ( \max_{x \in S} |u \cdot x| ).
   • This is an ( O(n \cdot k \cdot d) ) operation (n=10k points, k=direction count, d=dimensions), which is fast even for d=50.
3. Estimate the inscribed sphere radius
   • Calculate ( s_{\text{approx}} = \min_{u \in \text{direction set}} h_u ). This is a lower bound for the radius of the largest sphere centered at the origin that fits entirely inside the convex hull.

单点点判定流程 #

For each of your 2,000 test points ( p ):

1. Quick interior check (norm test)
   • Compute the Euclidean norm ( |p| ). If ( |p| < s_{\text{approx}} ), return definitely interior—the point lies inside the inscribed sphere, so it must be inside the convex hull.
2. Quick exterior check (support function test)
   • For each direction ( u ):
     • Calculate the dot product ( u \cdot p ).
     • If ( |u \cdot p| > h_u ), return definitely exterior—the point's projection in this direction exceeds the convex hull's bounds.
3. Unable to determine
   • If neither test returns a result, the point lies in a "gray area" near the convex hull boundary. Send it to your linear规划-based exact checker for final verification.

为什么这个方法有效？ #

• Norm test: The inscribed sphere is entirely contained within the convex hull, so any point inside it is guaranteed to be interior. This is lightning-fast (O(d) per point) and perfect for your use case where most points are interior.
• Support function test: For convex sets, if a point's projection in any direction falls outside the set's projection in that direction, the point must be exterior. This catches obvious exterior points quickly.
• Low false negatives: By adding more random directions, you can minimize the number of true interior points that fall into the "unable to determine" category—balancing speed and precision to fit your needs.

优化建议 #

• Parallelize preprocessing: Calculating support function values for each direction is fully parallelizable, which can cut down setup time significantly.
• Dynamic direction refinement: If you notice many "unable to determine" points, add new directions aligned with these points to improve future pre-check accuracy.
• Combine with your existing bounding box: The axis directions in your direction set already cover the bounding box check, so you can drop your separate bounding box step to avoid redundant work.

内容的提问来源于stack exchange，提问作者tommsch