Naj bo $P$ množica točk v ravnini. Za vsako točko $p\in P$ definiramo
\[\operatorname{cell}(p)=\{ x\in \mathbb{R}^2 \mid d(x,p)\leq d(x,p') \text{ za vsak }p'\in P\},\]kjer je $d(\cdot,\cdot)$ evklidska razdalja. Pokaži, da je $\operatorname{cell}(p)$ konveksna množica za vsako točko $p\in P$.
$\operatorname{cell}(p)$ je presek polravnin, torej konveksnih množic, in je zato tudi sama konveksna množica.
Konveksen večkotnik $M$ je podan kot seznam oglišč, naštetih v smeri urinega kazalca. Opiši algoritem, ki v linearnem času uredi oglišča večkotnika $M$ po $x$-koordinatah. Ali se da tvoj algoritem ustrezno dopolniti, da bo (še vedno v linearnem času) deloval za poljuben večkotnik $M$?
Za splošne večkotnike dokažimo, da če lahko urejamo oglišča v linearnem času, potem lahko urejamo poljubne sezname v linearnem času:
Tak algoritem potrebuje $\Omega(n \log n)$ - protislovje!
Opiši podatkovno strukturo za hranjenje konveksnega večkotnika $P$, ki omogoča, da v času $O(\log n)$ ugotovimo, ali je poizvedbena točka vsebovana v $P$. Konstrukcija podatkovne strukture mora biti izvedena v linearnem času.
Konstrukcija:
Poizvedba:
Podana sta dva konveksna večkotnika $P, Q$. Opiši algoritem, ki v linearnem času izračuna $\operatorname{CH}(P \cup Q)$. Če ne gre drugače, lahko predpostaviš, da sta $P$ in $Q$ disjunktna.
Podan je konveksen večkotnik $P$ kot tabela (array) oglišč $p[1, \dots, n]$.
def najvisja_tocka(p):
n = len(p)
def gor(i):
return p[(i+1) % n].y > p[i].y
i, j = 0, n-1
if gor(j) and not gor(i):
return p[i] # če je p[0] najvišja, bi jo v zanki zgrešili
while j - i > 1:
h = (i + j) // 2
if gor(i):
if gor(h) and p[h].y > p[i].y:
i = h
else:
j = h
else:
if gor(h) or p[h].y < p[i].y:
i = h
else:
j = h
if p[i].y > p[j].y:
return p[i]
else:
return p[j]