Newsgroup: it.hobby.enigmi
Titolo: 3n punti

Siano dati 3n punti sul piano in modo che non esista una terna di punti
allineati. Si possono costruire n triangoli che non si intersechino tra
loro e in modo che nessuno di questi triangoli sia contenuto in qualche
altro? 
Ciao



Non ho capito se i punti sono assegnati quindi hanno una distanza mutua fissata
oppure possono essere scelti a piacere. In quest'ultimo caso penso di si'.
Premetto che non ci ho pensato molto quindi posso sbagliare, cmq provo a dare
una dimostrazione costruttiva geometrica:
1) scegliamo la prima terna (A1,B1,C1) di punti non allineati in modo del tutto
arbitrario e costruiamo il triangolo T1(ABC);
2) costruiamo anche la circonferenza passante per i tre punti e sia C1(ABC);
3) scegliamo un punto arbitrario sulla circonferenza e tracciamone la tangente
t1  per quel punto; per fissare le idee supponiamo di prendere il punto piu'
lontano dall'origine di un riferimento cartesiano (posta a sinistra dei predetti
tre punti) in modo che la tangente alla circonferenza per quel punto sia una
retta parallela all'asse delle y; quindi una situazione di questo tipo:   O|
(la retta ovviamente sia tangente);
In questo modo il piano viene suddiviso da t1 in due semipiani, quello di
sinistra contenente la circonferenza C1 e, quindi, il triangolo T1 e quello di
destra vuoto;
4) nel semipiano destro vuoto scegliamo arbitrariamente tre punti (A2,B2,C2) non
allineati, costruiamo il triangolo T2(A,B,C) che trovandosi immerso nel
semipiano di destra non intersechera' il triangolo T1; costruiamo ora la
circonferenza C2(A,B,C)  [la quale potra' anche "sconfinare" nel semipiano di
sinistra, ma questo non ha importanza] e tracciamo la tangente t2 alla
circonferenza e parallela a t1 sempre nel punto piu' lontano dall'origine quindi
procedendo verso destra; avremo una nuova situazione tipo:   O|
5) ripetere il punto 4)  n volte per costruire n triangoli.
In questo modo, penso, che si giunga alla costruzione degli n triangoli
richiesti.
In questa costruzione si puo' verificare un caso limite quando un vertice del
triangolo T(i) sia il punto per dove passa la tangente t(i) alla circonferenza
C(i) ed uno dei punti del triangolo successivo T(i+i) coincida col precedente
vertice. In questo caso i due triangoli avranno un vertice in comune pur senza
intersecarsi.
Se si vuole evitare anche questa situazione e' sufficiente nella precedente
costruzione che una volta individuata la tangente t(i) si sostituisca
quest'ultima con la retta parallela  t(i)+epsilon   con  epsilon>0   in questo
modo si dovrebbero evitare anche i vertici in comune.
(ovviamente la costruzione, per semplicita',  procede da sinistra verso destra
con l'origine posto a sinistra di tutti punti; con opportune modifiche si puo'
procedere anche diversamente).
Ciao
gi@der             [< was it a cat I saw >]      (L. Carroll)

Ciao
Ho supposto che fosse implicito il seguente ulteriore
vincolo, altrimenti il problema era banale:
- ogni punto assegnato deve appartenere ad uno ed un solo
triangolo.
La risposta al quesito è affermativa, ed ecco un semplice
algoritmo risolutivo.
_________________
1.
Sia "V" l'insieme dei punti assegnati.
2.
Si prendono i 2 punti di V "p1" e "p2" tali che la retta
passante per essi divide il piano in 2 semipiani, l'uno
contenente un solo punto di V (sia esso "p3") e l'altro
contenente tutti i restanti punti di V.
Si costruisce il triangolo p1,p2,p3.
3.
Si pone
V := V - {p1,p2,p3};
se V <> Ø si torna al passo 2, altrimenti ci si ferma (ed il
problema è risolto ;-)
_________________
I 2 punti p1 e p2 di cui al punto 2 dell'algoritmo esistono
sempre.
DIMOSTRAZIONE:
Sia Conv(V) lo "Involucro Convesso"(*) dell'insieme V. Si
tolga un punto qualsiasi p3 di Conv(V), e si ridisegni
Conv(V-{p3}), il quale non può contenere p3, altrimenti
l'angolo interno di Conv(V) in p3 sarebbe stato >= 180°,
contro la definizione di Conv(V) e il vincolo sull'assenza
di 3 punti di V allineati.
Pertanto esistono certamente 2 punti consecutivi (o
adiacenti) p1 e p2 di Conv(V-{p3}), tali che la retta
passante per essi "separa" p3 e tutti gli altri punti di V,
dal momento l'unione di tutti i semipiani opposti a
Conv(V-{p3}) generati dalle rette per ogni lato di
Conv(V-{p3}), ricopre l'intera parte del piano esterna a
Conv(V-{p3}) (e quindi per forza contiene p3).
(*)
L'Involucro Convesso di V, è il poligono convesso di area
minima che racchiude tutti i punti di V.
Esso può essere visualizzato immaginando di
piantare dei perni in corrispondenza dei punti assegnati, e
di tendere un elastico attorno ad essi (l'elastico toccherà
quindi soltanto i perni più "esterni").
Ciao, Emanuele Z.