David Eppstein - Publications

Publications with Drago Bokal

• Finding all maximal subsequences with hereditary properties.
  D. Bokal, S. Cabello, and D. Eppstein.
  Proc. 31st Int. Symp. on Computational Geometry, Eindhoven, the Netherlands, June 2015.
  Leibniz International Proceedings in Informatics (LIPIcs) 34, pp. 240–254.

  We study problems in which the input is a sequence of points in the plane and we wish to find, for each position in the sequence, the longest contiguous subsequence that begins at that position and has some geometric property. For many natural properties we can find all such maximal subsequences in linear or near-linear time.

  (Slides)