кажется, доказал, что диаметр таки будет заключен между двумя вершинами.

Почему N^2? Просто N.

у диаметра 2 конца же, перебирать нужно оба

если многоугольник правильный, то нужно взять одну точку и найти наиболее удалённую от неё, это ~N

http://www-cgrl.cs.mcgill.ca/~godfried/research/calipers.html

во-первых, для правильного многоугольника можно за O(1) найти, если вершины упорядочены.

во-вторых, речь о многогранниках в 3d, произвольных

любопытно, но на 3d не распространяется. по кр. мере, неочевидно, как

Естессссно.

А можно предположение (только предположение), что нужно смотреть не каждую с каждой, а и n вершин 1 и n/2+1, 2 и n/2+2, т.е в случае прямоугольника это будут диагонали

Ой блэ, у тебя 3d

Тогда опять предположение, что нужно придумать метрику, по которой ты будешь находить наиболее отстраненные вершины, а дальше по плану машины

во-первых, для правильного многоугольника можно за O(1) найти, если вершины упорядочены.

А если ответ заранее дан, то вообще всегда за O(1) можно найти. В общем, не нужно херни нести. Если просто произвольный набор точек, то фит уравнения окружности (шара) через мнк, практически линейные уравнения получаются.

Если просто произвольный набор точек, то фит уравнения окружности (шара) через мнк, практически линейные уравнения получаются.

если можно, то же самое, по-русски.

кажется, доказал, что диаметр таки будет заключен между двумя вершинами.

не будет.

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

Диаметром множества M, лежащего в метрическом пространстве с метрикой \rho, называется величина (\sup_{x,y \in M}\rho(x, y)). Например, диаметр n-размерного гиперкуба со стороной s равен

Вопросы?

Уже нет.

Не может таки быть! Уж не знаю, как доказать, но по-моему, это будет расстояние между двумя точками на границе (если рассматривать эту фигуру и всё что «внутри» её как множество). Вот доказать, что эти точки будут именно вершинами затрудняюсь. А можете привести контр-пример? Т.е. где диаметр НЕ расстояние между вершинами

если можно, то же самое, по-русски.

Если диаметр нужен в смысле как ниже/выше только что написали, то так считать уже не нужно, нужно действительно искать наиболее удалённые точки.

не будет.

контрпруф в студию

Вот доказать, что эти точки будут именно вершинами затрудняюсь

таки легко. если конец диаметра на ребре, то минимум один из концов этого ребра будет дальше от второго конца диаметра. (геометрия внутри плоского треугольника)

если конец диаметра на грани - делаем произвольное сечение через диаметр; пересечение этого сечения с гранью рассматриваем так же, как с ребром

если конец диаметра внутри - тут очевидно. строго можно доказать, рассмотрев окрестность этого конца диаметра, лежащую целиком внутри многогранника

Я только что выдумал строгое математическое доказательство с немножечком матана и обычных аксиом метрики

И с одним (таки да!) лишь геометрическим фактом, что наиближайшее расстояние между точкой и прямой - это длина перпендикуляра

А можешь что-то большее сказать о своих фигурах? Выпуклые ли они или не обязательно?

они заданы набором вершин. выпуклые или нет не важно, если диаметр все равно на вершинах.

в принципе, можно ребра и грани задать, если это позволит отсортировать данные и ускорить перебор. задать можно в любом формате. многогранник может быть невыпуклым.

но я не в курсе, как можно отсортировать ребра и грани многогранника. разве что триангуляцией

Не, тогда я хз, увы

многогранник может быть невыпуклым

но ничто не мешает взять выпуклый многогранник на том же множестве вершин и найти его диаметр

esandmann, вдруг поможет? :)

Да не, у меня нет четкого плана. Я думал, что тут можно по аналогии с 2d - найти пары наиболее удаленных друг от друга вершин (в плане, что расстояние от одной вершины до другой - это минимальное количество вершин между ними, соединенных ребрами в ломанную, цитата из вики: >>Множество вершин любого связного графа G можно превратить в метрическое пространство, определив расстояние как минимальное число рёбер в пути, соединяющем вершины.<<).

Но в 2d вершины можно построить в список, отсортированный по этой метрике за O(N) и за O(N) найти ответ (если только фигура выпуклая). Это как в случае с прямоугольником - ты проверишь диагональ, а не стороны.

А в 3d так не выйдет, придется строить какой-то граф вместо списка и черт знает как это сделать. Так что увы, тут моя фантазия иссякла ;)

nlogn тебе

тебе ведь по сути нужно найти центр описывающий сферы , т.е найти пару наиболее удалённых вершин друг от друга.

это сортировка.

а значит nlogn

Я тут наврал с три короба, лол. Не работает такой метод даже для 2d.

это сортировка.

Чего сортировать будешь?

MyTrooName, решишь вопрос если, напиши сюда, оке?

на самом деле, вряд ли. скорее всего либо сделаю N^2, либо... я тут нашел намного более интересный матан, который может решить задачу :)

http://www.inf.ethz.ch/personal/gaertner/miniball.html

вершины в ЗD

октодеревья али ещё чё.

я тут нашел намного более интересный матан, который может решить задачу :)

Это оценки величины, именно твою задачу так не решить

спасибо!

там еще есть вот такая эвристика: In 1991, Emo W elzl dev elop ed a simple randomized metho d to solv e the problem in exp ected linear time [9]

[9]. Emo W elzl. Smallest enclosing disks (balls and ellipsoids). In H. Maurer, editor, New R esults and New T r ends in Computer Scienc e , v olume 555 of L e ctur e Notes Comput. Sci. , pages 359{370. Springer-V erlag, 1991.

Что такое диаметр многогранника?

то фит уравнения окружности (шара) через мнк, практически линейные уравнения получаются.

слово «практически» ЕМНИП лишнее. Я давно не занимался такой ерундой, но когда-то делал. Там не сложно на самом деле. Сначала находишь плоскость, а потом уже в плоскости сечения отыскиваешь прямую.

Другое дело, что ИМХО «диаметр многогранника» не нужен IRL.

если верно предположение, что диаметр будет заключен между двумя вершинами

Первое попавшееся определение диаметра из гугла: «диаметром многогранника называют наибольшую из длин всевозможных отрезков с концами в вершинах многогранника».

у меня, наверное, какой-то другой гугл)

если не трудно, посоветуй что-нибудь по этой теме:

книги по высчислительной стереометрии

Координаты вершин есть? Есть. Длину отрезков найдёт даже школьник из 7-го класса (найти из них максимальный - вообще не задача). Ты младше? Попроси свою учительницу тебя проконсультировать.

PS: что такое диаметр многогранника я вообще не понял. Думаю речь про главную диагональ.

что такое диаметр многогранника я вообще не понял

Попроси свою учительницу тебя проконсультировать

прочитай ОП еще раз, до конца. или с конца, если больше 1 предложения не осиливаешь

Курить здесь

Реализованная в CGAL эвристика Везля тут: http://doc.cgal.org/latest/Bounding_volumes/index.html#Chapter_Bounding_Volumes

Есть ещё алгоритм для окружности, с доказательством линейной сложности в книге http://libgen.org/book/index.php?md5=62A4A71032762D3D415C61FBF3D22DA4&ope... или в статье( http://theory.stanford.edu/~megiddo/pdf/lp3.pdf), но похоже что реализовать придётся самостоятельно.

http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_ss_07w/Webprojects/...

прочитай ОП еще раз, до конца. или с конца, если больше 1 предложения не осиливаешь

Прочитал, но так и не понял что ты имеешь в виду под диаметром многогранника. Приведи пример, что по твоему мнению является диаметром куба.

алгоритм нахождения длины диаметра для многогранника (3D) (комментарий)

для куба - главная диагональ

При чем здесь многогранник? Ты так сформулировал что непонятно может ли, например, диагональ пересекать грань.

Ты имел ввиду: как по заданным точкам (в трехмерном евклидовом пространстве ...), найти диаметр минимального замкнутого шара содержащего в себе все эти точки?

При чем здесь многогранник?

примерно при том же, при чем и ваш шар. другая формулировка той же задачи.

уже нашли решение, и не одно, а вы все о терминологии спорите

Твой вопрос стоит одного запроса в гугл, при этом около 30-ти постов из тебя пытались клещами выдрать нормальную формулировку, лол. На википедии есть статья, ровно по тому, что привел kamre (http://en.wikipedia.org/wiki/Smallest-circle_problem), для меня удивительно как он смог всего со второго раза понять что ты хочешь.

другая формулировка той же задачи.

Чушь.

Чушь

и то верно, smallest-circle problem тут ни при чем, нужен диаметр

около 30-ти постов из тебя пытались клещами выдрать нормальную формулировку, лол

дай мене 30 пруфов, лол