Computational Geometry

« nazaj

Računska geometrija - vaje 28.11.2024


Konveksnost

Naloga 1

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) = \bigcap_{p' \in P \setminus \{p\}} \{x \in \mathbb{R}^2 \mid d(x,p)\leq d(x,p')\}\]

$\operatorname{cell}(p)$ je presek polravnin, torej konveksnih množic, in je zato tudi sama konveksna množica.


Naloga 2

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!


Naloga 3

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:


Naloga 4

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.



Naloga 5

Podan je konveksen večkotnik $P$ kot tabela (array) oglišč $p[1, \dots, n]$.

  1. Opiši algoritem, ki v času $O(\log n)$ vrne najvišje oglišče iz $P$.
  2. Opiši algoritem, ki v času $O(\log n)$ vrne obe tangenti večkotnika $P$ skozi podano točko $p\in \mathbb{R}^2 \setminus P$.
  3. Opiši algoritem, ki v času $O(\log n)$ vrne presečišče med $P$ in podano premico $\ell$.
  4. Opiši algoritem, ki v času $O(\log n)$ vrne točko iz $P$, ki je najbližja podani premici $\ell$.


  1. 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]