无洞多边形全可见点集的O(n)时间空间算法可行性咨询

Great question! First off, let's clarify the key term here—what you're searching for is called the kernel of a simple (hole-free) polygon: the set of all interior points from which every other point in the polygon is fully visible.

And the short, definitive answer is: Yes, there absolutely exists an O(n) time and space algorithm to compute this kernel!

The classic solution here is the Lee-Preparata algorithm, published in 1979, which is designed specifically for simple polygons and runs in linear time. Here's a high-level breakdown that aligns with your thought of working along the polygon boundary:

• Start by initializing the kernel as the half-plane defined by the polygon's first edge (we only keep the side that lies inside the polygon, naturally).
• Iterate through each subsequent edge of the polygon, and iteratively clip the current kernel to the region of points that maintain full visibility relative to that edge. Because we process edges in the order they appear along the polygon's boundary, we don't need the more costly O(n log n) general half-plane intersection algorithm—this clipping can be done in linear time as we go step by step.
• Once all edges are processed, the remaining region is exactly the polygon's kernel: every point in this set can see every part of the polygon, and no points outside this set have that full visibility.

A quick note: this linear-time result only applies to simple, hole-free polygons. If you introduce holes into the polygon, the problem becomes more complex, and linear time is no longer achievable.

Also, since you mentioned planning to add diagrams later—visualizing how each edge narrows down the potential kernel region is a fantastic way to grasp why this algorithm works. Each step trims away points that can't see some part of the polygon, leaving only the maximal region of full visibility by the end.

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