In microlithography, mask patterns are first fractured into trapezoids and then written with a variable shaped
beam machine. The efficiency and quality of the writing process is determined by the trapezoid count and
external slivers. Slivers are trapezoids with width less than a threshold determined by the mask-writing tool.
External slivers are slivers whose length is along the boundary of the polygon. External slivers have a large
impact on critical dimension (CD) variability and should be avoided. The shrinking CD, increasing polygon
density, and increasing use of resolution enhancement techniques create new challenges to control the trapezoid
count and external sliver length. In this paper, we propose a recursive cost-based algorithm for fracturing which
takes into account external sliver length as well as trapezoid count. We start by defining the notion of Cartesian
convexity for rectilinear polygons. We then generate a grid-based sampling as a representation for fracturing.
From these two ideas we develop two recursive algorithms, the first one utilizing a natural recurrence and the
second one a more complex recurrence. Under Cartesian convexity conditions, the second algorithm is shown to
be optimal, but with a significantly longer runtime than the first one. Our simulations demonstrate the natural
recurrence algorithm to result in up to 60% lower external sliver length than a commercially available fracturing
tool without increasing the polygon count.