Главная страница


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Serge Kanilo                         2:5020/400     08 May 2001  01:26:34
 To : All
 Subject : Re: Треугольник  наименьшей   площади
 -------------------------------------------------------------------------------- 
 
 Hi Andrey,
 
 "Andrey Paniukov" <Andrey.Paniukov@p13.f64.n5054.z2.fidonet.org> wrote in
 message news:989264767@p13.f64.n5054.z2.FIDOnet.ftn...
 
 >  SK> И какой интересно треугольник минимальный площади,
 >  SK> описанный вокруг квадрата? Что должно получиться я то знаю,
 >  SK> но каким образом приведенный алгоритм справится с такой задачей?
 >
 >  SK> Да и если точки на одной прямой, решение вырождается, чего нет в
 >  SK> задаче об окружности.
 > Естественно не все так же, но первая стадия _И_М_Х_О_ та же, т.е.
 
 выявление
 
 > многоугольника, т.к. с остальными точками работать незачем.
 
 Hасколько я понял ты считаешь, что построение охватывающего выпуклого
 многоугольника (возможно и приводящее к  уменьшению количества точек)
 упростит определение окружности. Hо как кто-то уже не раз указывал в том
 обсуждении, задача построения окружности вокруг множества точек гораздо
 проще, чем задача построения охватывающего многоугольника.
 Первая - линейно зависит от количества точек, вторая - квадратично.
 
 > Дальше задача сведется к тому что бы описать минимальный тр. вокруг
 > многоугольника.
 
 Для данной задачи, по видимому, построение охватывающего многоугольника
 является необходимым шагом.
 
 > А это уже другой вопрос;))
 > Тут должна быть закавыка иначе гемор полнейший.
 
 Да, задачка не из легких :) - помесь дискретной и непрерывной минимизации.
 Единственно, что можно утверждать - что на каждой грани треугольника будет
 по крайней мере по одной точке, а на одной - хотя бы две.
 
 > Такое предположение: может в качестве вершины брать одну из точек.
 
 Я всегда пробую проверить каждое предположение на хотя бы нескольких
 вариантах данных.
 Данное предположение проверим на вершинах правильного шестиугольника.
 Решение для минимального охватывающего треугольника очевидно,
 но ни одна вершина треугольника не совпадает с одной их исходных точек.
 
 > Bue Serge!
 
 Bye,
 
 Serge
 
 --- ifmail v.2.15dev5
  * Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Re: Треугольник наименьшей площади   Serge Kanilo   08 May 2001 01:26:34 
 Треугольник наименьшей площади   Andrey Paniukov   09 May 2001 00:20:48 
Архивное /ru.algorithms/210679841d988.html, оценка 2 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional