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.