The efficiency of the KIRKPATRICK point location method depends heavily on the choice of the set of points to be removed during a hierarchy construction step.
Let 
be a star-shaped polygon with 
vertices, whose center point has
been removed. Before center point removal the polygon was triangulated with
triangles. The degree of the center point (i.e. the number of edges
which are connected to that point) is also . After removing the center
point, 
triangles are created during retriangulation of the polygon. The
``yield'' (i.e. the percentage of removed triangles per grid hierarchy
construction step) is therefore 
, provided that all triangles are
selected during a construction step and no triangles need to be promoted to
the next hierarchy.
Now all points of a degree less than are selected for removal in a
grid hierarchy. This criterion suffices to proof that it is indeed possible to
construct a finite SDAG [Prep85].
The choice of this constant is critical to the performance of the
algorithm. can not be smaller than three, because the minimum degree of
any inner point in a triangulation is three. But there is no upper bound for
, since the maximum degree of a point is theoretically unlimited in a
triangulation. Choosing to be relatively large results in many points
being selected during each step, hence creates few hierarchies and a ``low''
SDAG. But the number of references held by each inner node of the SDAG
is at most 
, and therefore equally large. On the other hand, choosing
to be relatively small results in fewer points being selected for removal, and
therefore creates a ``higher'' SDAG but with less references per inner
node.
Taking a closer look on the yield defined above, we see that it can be at most
two thirds for 
(degree is three) and approaches one for higher . An
analysis of typical unstructured grids occurring in TCAD applications
reveals that the majority of vertices has a degree of six to eight. Choosing a
therefore of six to eight results in a good yield while maintaining a
reasonable amount of selectable vertices.