Esercizi sulla ricorsione

[stefano_89]

Ciao a tutti, mi sono imbattuto in 2 esercizi d' esame molto simili ma da cui non riesco proprio a venir fuori. Sono da risolvere entrambi con la ricorsione, e non serve codice java, ma solo pseudo-codice, ora riporto il testo:

Sia dato un insieme di n punti nel piano (non coincidenti). Un albero KBD è un albero binario così definito: se n = 1, la radice dell' albero contiene il punto corrispondente. Se n > 1, la radice dell' albero contiene la linea veritcale (oppure orizzontale) passante per un punto dell' insieme, il sottoalbero sinistro è un KBD costruito sull' insieme dei punti a sinistra (in alto) rispetto alla linea della radice e il sottoalbero destro è un KBD costruito sull' insieme dei punti a destra (in basso) rispetto alla linea nella radice. Si noti che la linea è alternativamente verticale e orizzontale per valori di profondità crescente. Progetare un algoritmo ricorsivo per costruire un KBD, dato un insieme di n punti nel piano e valutare la sua complessità computazionale.


Sia I un insieme di n punti non coincidenti nel piano, Un inviluppo convesso di I è il più piccolo insieme convesso che contiene tutti gli elementi di I. Se n =1, l' inviluppo convesso di I è lo stesso I. Se n > 1, l' inviluppo convesso di I si ottiene applicando la funzione UNION agli inviluppi convessi di J e K, con J $uuu$ K = I e J $nnn$ k = 0 (insieme vuoto). Progettare un algoritmo ricorsivo per costruire l' inviluppo convesso di un insieme di n punti nel piano (n potenza di 2) e valutare la sua complessità computazionale (la funzione UNION è data per ipotesi).

Ora, il problema sta nel trovare il caso base, e quella che sarà la parte ricorsiva. Ho pensato che, a grandissime linee, si dovrà in entrambi fare ricorsioni fino a quando non si rimane con un solo punto a disposizione, e poi andare a ritroso.
Ma ci sono vari problemi:
- nel primo esercizio, dovrò mettere un' istruzione "if" per chiedermi se sopra, sotto, a destra o sinistra sono rimasti "n > 1" punti. Inoltre, come faccio ad alternare la scelta orizzontale-verticolare o la scelta sopra-sotto. Infine, come sceglierie il successivo punto su cui fare la ricorsione, il più vicino alla linea scelta?

- nel secondo esercizio, boh, faccio fatica a capire ciò che si deve fare. In teoria dovrei ricreare quei 2 inviluppi convessi disgiunti J e K. Però non so neanche con che criterio scegliere i punti su cui fare la ricorsione.

Qualcuno può darmi una mano ?

Grazie in anticipo!

[apatriarca]

Per quanto riguarda il primo esercizio, si può dividere il passo ricorsivo in diverse fasi. Ad ogni passo è infatti necessario scegliere per prima cosa il punto per il quale tracciare la linea, poi si deve dividere l'insieme dei punti in due gruppi distinti e infine si deve richiamare la funzione sulle due partizioni create. La prima fase è quella più delicata e che determina maggiormente la complessità dell'algoritmo scelto. Determina infatti quanto bilanciato sarà l'albero e concorrerà nel costo computazionale del singolo passo ricorsivo. Alcune possibili scelte sono ad esempio quelle di scegliere il punto a caso, scegliere il primo punto dell'insieme di punti, scegliere il punto mediano tra 3 punti scelti a caso o meno, scegliere il punto mediano dell'insieme..

Quando si calcola l'inviluppo convesso è spesso utile ordinare preventivamente i punti e poi creare l'algoritmo basandosi su questo ordine. Il punto più critico di questo algoritmo è a mio parere il "merge" dei due sottoinviluppi. E' un algoritmo molto discusso sui libri di geometria computazionale (anche l'altro in effetti).

[stefano_89]

grazie della risposta,visto che sono esempi molto discussi, sono andato a spulciare un pò di questa geometria computazione. Ho trovato questo pdf ben fornito: http://profs.sci.univr.it/~fusiello/tea ... eocomp.pdf

A pagina 117 parla del k-d tree e riporta il codice, che copio:

KDNode insert(PointSet P) {
  t = new KDNode;
  
  if (#P = 1) /* create a leaf */
    t.point = unique point in P;
    t.left = NIL; t.right = NIL;
  
  else /* create an internal node */
    t.cutDim = choose cut dimension;
    t.cutVal = median(P, t.cutDim);
    t.size = #P;
    split P in P1 and P2 with t.cutDim and t.cutVal;
    t.left = insert(P1); t.right = insert(P2);
  
  return t
}

Anche il testo parla di considerare alternativamente le coordinate x,y (cosa più che altra imposta dal testo del problema) e di usare il punto medio tra quello a cui si è arrivati e il margine della regione immagino. Nonostante la brevità del codice, non mi è del tutto chiaro. Inizialmente si pone il caso base: se il numero dei punti rimaneti è 1, allora metti il punto come foglia. Altrimenti, e qui viene il problema, "t.cutDim = choose cut dimension; " cosa significa: scegli la dimensione del taglio ? forse per dimensione intende la coordinata ? ma è strano, perchè altrimenti si discriminerebbe sempre con la stessa variabile. Poi c'è "t.cutVal = median(P, t.cutDim); " in cui pare si scelga il punto medio utilizzando i punti rimasti e t.cutDim, che pare sia proprio la coordinata discriminante. Si passa a "t.size = #P; " che sarebbe anche semplice come istruzione, ma non capisco a che serve.

Per il secondo esercizio sono ancora in alto mare..

[apatriarca]

Scusa se non ti ho risposto prima, ma ero in vacanza. Non conoscevo la dispensa che hai postato. I testi a cui faccio normalmente riferimento sono:
- de Berg et aliis, "Computational Geometry", Springer-Verlag, 1997
- O'Rourke, "Computational Geometry in C", Cambridge Press, 2001

Nelle pagine precedenti al codice viene spiegato che "cut dimension" è la coordinata considerata (la direzione della retta). Il modo più semplice per alternare le coordinate è passare la coordinata usata precedentemente alla funzione come parametro e quindi alternarla ad ogni successiva chiamata. Un altro modo è quello di usare due funzioni diverse per le due direzioni. Con #P si indica semplicemente la dimensione dell'insieme dei punti. Viene memorizzata per comodità.

Per il secondo dai un occhiata a questo link: http://www.cse.unsw.edu.au/~lambert/jav ... nquer.html