25
правок
Изменения
Нет описания правки
Описанный процесс можно реализовать как в виде рекурсивной процедуры, расслаивающей множество вдоль очередной координаты и вызывающей себя рекурсивно для каждой части и следующей координаты, так и нерекурсивно, если поддерживать множество всех текущих частей и на очередной итерации разбивать их все вдоль очередной координаты.
Время работы алгоритма напрямую зависит от суммарного количества частей, на которые будет разбито исходное множество.По аналогичным предыдущему алгоритму рассуждениям легко показывается, что частей не более <tex>n^d</tex>. Тем не менее, существует более точная оценка. {{Теорема |statement=Суммарное количество частей, полученных алгоритмом HSO, не превышает <center><tex>f(n, d) = {n + d - 2 \choose d - 1}</tex>.</center> |proof=База: <center><tex>f(n, 1) = 1</tex>.</center> Также, из алгоритма расслоения следует, что из части с <tex>n</tex> точками будет получено по одной части для каждого <tex>i = 1...n</tex>, то есть: <center><tex>f(n, d) = \sum \limits_{i = 1}^{n}f(i, d - 1)</tex>.</center> }}
