Прямая призма наибольшего объёма

@Gendos1976 · Регистрация: 23.10.2015

Студворк — интернет-сервис помощи студентам

Доброго времени суток, долго думаю над эффективным алгоритмом для решения задачи, может кто идейку подкинет.
Задача: есть массив точек в пространстве, необходимо выделить из этих точек прямую призму наибольшего объёма.
С чего лучше начать? Как вариант думал выделить все возможные прямоугольники и из них пытаться выделить прямую призму. Но эффективность крайне низкая. Алгоритм O(n^3) в лучшем случае.

@Symon · 13.10.2016, 15:29

Сообщение от Gendos1976

выделить из этих точек прямую призму

Эти слова требуют уточнения. Вершины призмы являются точками данного множества? Боковые ребра призмы параллельны какой либо оси координат? ...

@Gendos1976 · 13.10.2016, 15:31 **[ТС]**

Да, вершины призмы являются точками данного множества. Расположена может быть как угодна(не задана паралелльность рёбер чему либо).

@Gendos1976 0 / 0 / 0 Регистрация: 23.10.2015 Сообщений: 6
		1
	Прямая призма наибольшего объёма 13.10.2016, 14:36. Показов 598. Ответов 2 Метки нет (Все метки) Доброго времени суток, долго думаю над эффективным алгоритмом для решения задачи, может кто идейку подкинет. Задача: есть массив точек в пространстве, необходимо выделить из этих точек прямую призму наибольшего объёма. С чего лучше начать? Как вариант думал выделить все возможные прямоугольники и из них пытаться выделить прямую призму. Но эффективность крайне низкая. Алгоритм O(n^3) в лучшем случае. 0

@Symon $Эксперт по математике/физике$ 2615 / 2229 / 684 Регистрация: 29.09.2012 Сообщений: 4,578 Записей в блоге: 13
	13.10.2016, 15:29	2
	Сообщение от Gendos1976 выделить из этих точек прямую призму Эти слова требуют уточнения. Вершины призмы являются точками данного множества? Боковые ребра призмы параллельны какой либо оси координат? ... 0

@Gendos1976 0 / 0 / 0 Регистрация: 23.10.2015 Сообщений: 6
	13.10.2016, 15:31 [ТС]	3
	Да, вершины призмы являются точками данного множества. Расположена может быть как угодна(не задана паралелльность рёбер чему либо). 0

Опции темы