Posted By: vitas (Love, peace and Coyot) on 'CZscience' Title: Re: Prumer konvexniho polygonu Date: Mon Jan 4 23:23:38 1999 cao chvilku jsem premyslel ... a nic. nicmene kamos vymyslel peknou optimalizaci... pozorovani: dejmentomu ze prumer je tvoren useckou a_i a_j potom vsechny body (spec. vrcholy) polygonu lezi v pasu kolmem na a_ia_j (s hranicnimi body a_i, a_j). tedy naopak: pokud by v a_i mel jeden z vrcholu prumeru musi byt uhel a_{i-1}a_ia_j ostry (presneji: netupy), podobou uvahou i uhel a_{i+1}a_ia_j. na prohledani ti tedy zbyde jen mala vysec. casova slozitos: vysec najdes v log n, musis projit n/2 bodu. a jeste nejaky cas stavis prochazenim vysece. ten vsak nejsem schopen odhadnout. i kdyby vsak byl v souctu maly (tj do n log n). tak vysledna casova slozitost je n log n nic moc, ale lepsi nez batohem do hamiltonovi kruznice. -- vitas @;; > potreboval bych algoritmus, ktery najde prumer konvexniho polygonu v > rovine > v linearnim case vzhledem k poctu vrcholu. (Prumer je vzdalenost > nejvzdalenejsich vrcholu). Staci slovne popsat, nepotrebuju implementacni > detaily.