Уточнение разделов - это техника, в которой вы начинаете с конечного набора объектов и постепенно разбиваете набор. Некоторые проблемы, такие как минимизация DFA, могут быть достаточно эффективно решены с помощью уточнения разделов. Я не знаю никаких других проблем, которые обычно решаются с помощью уточнения раздела, кроме тех, которые перечислены на странице Википедии. Из всех этих проблем на странице Википедии упоминаются два, для которых алгоритмы, основанные на уточнении разделов, выполняются за линейное время. Есть лексикографически упорядоченная топологическая сортировка [1] и алгоритм лексикографического поиска в ширину [2].
Существуют ли другие примеры или ссылки на проблемы, которые могут быть решены с помощью очень эффективного уточнения раздела, что означает нечто лучшее, чем логлинейное с точки зрения времени?