weakness of the slab decomposition is that the vertical lines create additional segments in the decomposition, making it difficult to achieve O(n) storage space. Herbert Edelsbrunner, Leonidas J. Guibas, and Jorge Stolfi discovered an optimal data structure that only uses the edges in a monotone subdivision. The idea is to use vertical monotone chains, instead of using vertical lines to partition the subdivision.

Converting