I am trying to implement the kernel finding algorithm proposed by D.T. Lee and F.P. Preparata and I'm having trouble understanding why this algorithm runs in O(n) rather than O(n²), where n is the number of vertices in the polygon.

In very short words, the algorithm involves removing from a plane K the section that is not "visible" from a vertex v_i by intersecting K with one of the half-lines passing through v_i and v_{i 1}.

In order to compute the intersection, parsing the edges of the plane K is required. The number of edges in K is less than n, but not constant, and such the intersection must take O(n). This is confirmed by the authors: "the total number of vertices visited by the algorithm in handling case (1.1), is bounded above by 3n, Le. it is O(n)"

In the case that the kernel of the polygon exists, such intersections need to be computed for each vertex composing the polygon. So I'm expecting the total time complexity to be O(n²).

The paper describes an additional test but as far as I understand it only serves in terminating the algorithm early if the polygon does not have a kernel.

I'm missing something for sure but I'm not able to determine what.

CodePudding user response：

By a rough reading of the article, I understand that the kernel is built incrementally one edge at a time. When an edge causes the removal of a part of the kernel, the intersections of the half-plane of support with the kernel are found by a linear search along the kernel from an F or L vertex. So I imagine that

• the total cost of the linear searches is bounded by O(n), because if a search involves several vertices, it will reduce the size of the kernel accordingly, making the future steps "more bounded";

• after a removal, the F and L vertices can be quickly updated.

In other words, the update of the kernel implied by a new edge is done in amortized constant time.