Decomposing Points Into Non-crossing Monotonic Descending Chains

by Francisco Claude

A recent proposal by Arroyuelo et al. showed how decomposing a set of points
into monotonic descending and ascending chains allows for an adaptive data
structure for answering range search queries in O(k log n + m) time, where k is
the number of chains the set is decomposed into and m the size of the output.
Furthermore, if we decompose the points into chains that do not cross, the time
can be improved to O(log n + k + m).
In 1989 Supowit proposed an optimal time algorithm for partitioning a set of
points into monotonic descending chains.  In this work we explore how to
generate the minimum number of non-crossing descending chains, and present an
O(kn log n + nk^2) time algorithm for this problem.  We will cover the
theoretical proposal together with some preliminary experimental results.

Joint work with Diego Arroyuelo, Reza Dorrigiv, Stephane Durocher, Meng He,
Alejandro Lopez-Ortiz, J. Ian Munro, Patrick K. Nicholson, Alejandro Salinger
and Matthew Skala.