2026-08-16T11:49:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5113 2024-03-06T10:35:52Z ddc:004 open_access

Finding All Maximal Subsequences with Hereditary Properties Bokal, Drago Cabello, Sergio Eppstein, David convex hull diameter monotone path sequence of points trajectory Consider a sequence s_1,...,s_n of points in the plane. We want to find all maximal subsequences with a given hereditary property P: find for all indices i the largest index j^*(i) such that s_i,...,s_{j^*(i)} has property P. We provide a general methodology that leads to the following specific results: - In O(n log^2 n) time we can find all maximal subsequences with diameter at most 1. - In O(n log n loglog n) time we can find all maximal subsequences whose convex hull has area at most 1. - In O(n) time we can find all maximal subsequences that define monotone paths in some (subpath-dependent) direction. The same methodology works for graph planarity, as follows. Consider a sequence of edges e_1,...,e_n over a vertex set V. In O(n log n) time we can find, for all indices i, the largest index j^*(i) such that (V,{e_i,..., e_{j^*(i)}}) is planar. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Drago Bokal and Sergio Cabello and David Eppstein 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.240 urn:nbn:de:0030-drops-51132 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.240 eng https://creativecommons.org/licenses/by/3.0/legalcode