i
i
“1268-Indihar-krog” — 2010/7/22 — 14:09 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 23 (1995/1996)
Številka 5
Strani 294–297
Stane Indihar:
NAJMANJŠI KROG
Ključne besede: matematika, ravninska geometrija, C-P algoritem, tri-
kotniki, krogi.
Elektronska verzija: http://www.presek.si/23/1268-Indihar.pdf
c© 1996 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
Mat ematika I
NAJMANJŠI KROG
1. U vo d
V lanski 4. številki Preseka je na st ra ni 213 Mar tin J uvan zastavil nasled-
njo nalogo:
Opiši algoritem, ki za dano končno mn ožico točk v ravnini poišče
krog z najmanjšim polm erom , ki vsebuje vse točke iz mn ožice. Algoritem
naj bo čim učinkovi tejši (in tudi dovolj preprost , da ga j e mogoče brez
prevelikih težav sprogramirati).
V naslednji številki Preseka pa je bil na straneh 296, 297 objavljen
J uvanov algoritem, kako takšen krog poiskati .
Ker ima omenje na naloga kar precejšnjo zgodovino in tudi posp lošit-
ve, spregovorimo o njej nekoliko obširneje.
V literaturi najdemo podatek , da je nalogo v letu 1857 zastavil J . J.
Sylvester . Tri let a zatem je konstrukcijsko rešitev podal B. Peirce, v letu
1885 pa je do enakega postopka kot Peirce pri šel tudi G. Chryst al. Njun
pr istop k reševanju na loge je sedaj znan pod imenom Chrystal - Peirceov
algor item (C-P algoritem) . Ogledali si ga bomo pozneje.
Zanimanje za nalogo se je spet poj avilo po dr ugi svetovni vojni z
razvojem ope racijskega raziskovanja in matematičnega programiranja . V
prvo področje sodi np r . naslednj a prakt ična naloga:
Kj e naj postavim o urgentno helikopt ersko reševalno postajo, da bo
razdalja do najbolj oddaljenega kraja čim manjša?
Pri tej nalogi imajo vsi kraji enako "težo". Če pa up oštevamo, da so
kraj i lahk o različno "obteženi" , dobimo splošnejšo nal ogo. Kot krit erij za
raz lične obtežitve je npr . število prebivalcev.
Posplošitev Sylvestrove naloge dobimo tudi, če nam esto mn ožice točk
v ravni ni vzamemo končno množico točk v 3-razsežnem ali pa kar n-
razsežnem prostoru (n ~ 3) . V tem primeru iščemo n-razsežno kroglo
z najmanjšim polm erom, ki vsebuj e vse točke dane mn ožice. To nalogo
st a J . Elzinga in D. W. Hearn prevedla v posebni problem nelinearnega
programiranj a , ki je rešljiv v končno mn ogo korakih.
2. c-p algoritem
Osnovan je na naslednji očitn i lastnosti trikot nika:
- za topokot ni (ali pravokotni) trikotnik j e najd aljša stranica hkra ti
premer najmanjšega kroga, ki trikotnik vsebuje;
- za ostrokotni (ali pravokotni) trikotnik j e najmanjši krog, ki vsebuje
ta trikot nik , kar njemu očrtani krog;
I Aiatematika
in na izreku :
Naj bo A BC topokot ni triko tnik s topim kotom pri oglišču B in
točka D zno traj trikotniku ABC očrtanega kroga I<. Če j e kot <t ADC <
< <tABC , potem im a trikotniku ADC očrtani krog K 1 m anjši polm er,
katje polm er kroga K , in v K1 se nahaja tudi točka B .
]{
A
Dokaz izreka. Na sliki j e točka O središče kroga K , točka 0 1 pa
središče kroga K 1 . Središči obeh krogov sta na simetrali s daljice AC.
Ker je točka D znotraj kroga K , seka sim etrala S l daljice C D (na tej
simetrali j e središče kroga K d simetralo s v točki 01, ki se nahaj a med
točko O in razpoloviščem daljice AC. Krog J(1 ima zato manjši polm er ,
kot j e polmer kroga J( , in celot ni lok ABC br ez krajnih točk je znotraj
kroga K 1 , torej t udi točka B .
Preidimo sedaj na prikaz C-P algoritma.
Naj bo S končna množica točk v ravn ini . Iščemo najmanj ši krog , ki
to množico vsebuje .
Korak O (začetni korak). Narišemo krog, ki pot eka skozi dve točki A ,
B množice S in vsebuj e vse točke te množice.
Korak 1. Med točkam i množice S - {A , B} poiščemo točko , pri ka-
teri j e kot <tADB najmanjši. Najdeno točko (ki morda ni eno!ično
določena) označimo s C.
a) Če j e <tAC B 2': ~ j e naloga rešena. Daljica AB je pr emer naj -
manjšega kroga , ki vsebuj e množico S .
b) Če j e <tACB < ~ preidemo na nas lednji korak .
Matematika I
Korak 2. Tr ikotniku ABC očrtamo krog.
a) Če trikot nik A BC ni topokote n, je naloga rešena . Njegov očrtani
krog je najmanj ši krog, ki vsebuje mn ožico S.
b) Če je ABC topokot ni trikotnik, odstranimo izmed točk A, B
tist o, pri kat eri je topi kot - naj bo to npr . točka B - in preidemo
na korak 1, pri katerem točko B zam enj a točka C.
Skladno z izrekom bo vsak naslednji krog, ki ga konstruiramo, manj ši
od predhodnega in bo vsebova l vse točke mn ožice S . Pri iskanju naj-
manjšega kot a v prvem koraku pa ni treba več up oštevati točk, ki jih
odstranimo v drugem koraku . Ker je točk množice S končno mnogo in se
pri vsaki ponovitvi iskanj a manj šega kroga, ki vsebuje množico S, polmer
zmanjša, je algoritem končen .
V zvezi z začetnim korakom , ki je nekako nedorečen , sta R. K. Cha-
kraborty in P. K. Cha udhur i (1981) predlagala poseben postopek , po ka-
terem najdemo z ačetni par točk A , B . Prav tako st a opazila, da v drugem
koraku lahko poleg točke B odstranimo iz nad aljnj ih računov oziroma
konstrukcij t udi vse tiste točke D ES - {A , C }, pri katerih je <lADC topi
kot .
Računske izkušnje, do katerih st a pri preskuš anju algorit ma prišla
avto rja članka , ki je naveden v uvodu, so zelo ugodne. Število točk v
množici S je bilo med 100 in n oa. Število operacij je bilo sorazm erno s
številom točk v mn ožici S .
3. Zaključek
Da bi bil prikaz reševanj a Sylvestrove naloge popolnejši, navedimo še
naslednj e.
V delu B. J. Oommen, An Efficient Geometric Solution to the Mini-
mum Spanning Circle Problem , Operations Research 35(1987)1, 80-86, je
prikazan algoritem, ki izboljša tudi korak 2b v P- C algoritmu. Pri vseh
računskih posku sih , razen v zelo redkih izjemah, je bil s tem algorit mom
naj m anjši krog najden v natanko dveh iteracijah. Oommen navaj a , poleg
drugih dosežkov, tu di metodo , ki jo je razvil N. Megiddo (1982) . Problem
naj m anj šega kroga Megiddo prevede v dvora zsežni problem linearnega
progra miranja in ga reši v času, ki je linearno odvisen od števila točk.
Zani mivo je omenit i , da je Oom men svoj algoritem preskušal tudi pri
iskanju najmanj ših krogov , ki objemajo Velika jezera Severne Amerike.
1. Kje ja lDedisEe lu4jmaqjbga kroga, ki mbqje SCooenijo merja) 
in koWn je njagov pober? 
2. Kab hi pojsksJi n4val4ji k g *  ki ga lahlco vrilZemo v Slovenijo? 
Pn'pomdki: Uvlodna M a  v Atlam m e ,  prommi papir, da nanj 
preaem d d  nn*,.ramnikr, Beetilo. 
Prf rdemqju 1. ndage dobimo toElao, ki je b h  b n & d m .  Od 
geomet$.heg(~ a r d S &  Qlmde (GEOSS) je odd-a pribko 12 km. 
Todm GEOSS, ki se nahaja pri Spodqji Slivni Bahodno od VaE, pomeni 
n m &  t& liJsa, ki b a  obliko Slovenije. 
Stane Inaar