Ponthalmaz lefedési probléma

Hat, egy egyszeru megoldas az az, hogy O(n*log(n)) ido"ben meghatarozod a ponthalmaz Delaunay-haromszogele'se't, majd ebbo"l szarmaztatod a konvex burkot (azaz azon pontok halmaza't, melyek nem teljesen koruljarhatoak), ez pedig O(n) ido"ben tuti megvan, amennyiben a haromszogelesi info adott. A wikipedia: konvex burok szerint viszont enne'l jobb ido"ben nem lehet meghatarozni, vagyis O(n*log(k)) ido"re le lehet vinni, ahol k a burok pontjainak sza'ma, de ez altalanos esetben sqrt(n), azaz O(n*log(sqrt(n))=O(n*log(n)/2)=O(n*log(n)), lenyegeben ugyanaz.

A delaunay-haromszogelesre van progim (c-ben), a divide & conq modszer, minden jarulekos infoval egyutt, abbol csak meg lehet ma'r egyszeru"en csinalni konvex burkot (vagy direkte a 3 lefedo" egyenest), de arra nem tudok progit hirtelen.

A.

Nem teljesen értem a feladatot:
- síkban adott egy ponthalmaz,
- ennek keressük lefedését 3 egyenessel
Nekem ez azt jelenti, hogy találjunk minél több pontot lefedő egyeneseket (kollineáris pontokat).

Viszont a fenti válaszból illetve a konvex burok keresésből arra következtetek, hogy a "lefedés" itt határolás, tehát 3 egyenessel akarjuk határolni a ponthalmazt, és ezek illeszkedjenek pontokra ???

Tipp:
Az ilyen jellegű problémák megoldása, olyasmi szokott lenni, hogy megnézzük szomszédos pontokhoz milyen meredekségű/szögű szakasz tartozik (pl. csak lentröl felfelé haladva), és ezt rendezzük valahogy, aztán ebböl probálunk egyeneseket vadászni.

Hirtelen ennyi jutott eszembe, ilyesféle irányba probálkoznék elsőre.

-

Azert nem olyan nehez ez, tessek gondolkodni. Tavaj ue a feladatot a Moszka terol a Jaszaig oldottam meg a villamoson.

-Hogyan tudod osztalyozni a pontok halmazat ?
-Mivel tudod gyorsan eldonteni, hogy 3 pont egy egyenesen van (egesz szamok) ?
-Hogyan tudod gyorsan kiszamolni, hogy egy pont melyik osztalyba kerul ?
-Hany pontot kell beolvasnod minimum, hogy meghatarozd a halmazokat ?

Tobbet nem segitek.

g

Hangosan gondolkodom:

Ha a 3 egyenes minden pontot lefed, akkor bármelyik 6-ot is.
Pillanatra tegyük fel, hogy kiválasztottunk 6 pontot úgy, hogy csak 2-2 van egy egyenesen.
Ekkor van konstans számú variációnk egyenesekre (a 6 pontot hányféleképpen lehet összekötni), és csak azt kell kipróbálni, hogy ezek közül melyik fedi le az n pontot.
Ez nyilván O(n).

Már csak ki kell választanunk a 6 pontot úgy, hogy csak 3 egyenessel lehessen lefedni. (Ha ilyen nincs, akkor a teljes ponthalmaz lefedhető 3-nál kevesebb egyenessel.)
Na most érzésem szerint ez is O(n)-ben megoldható. Max tévedek. :)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Gondoltam agyalok egy kicsit, ha haza jöttem, de látom már megoldottátok :)

bár már biztos megoldottátok 3-ra, most legyen k egyenesünk. tudtok-e O(k*n)-nál jobb algoritmust?

Nekem is van egy O(n)-es megoldásom, ha n pont van, melyek elemei k db egyenes uniójának. Az O() becslésben k-t konstansnak veszem, ami kicsit fényezi a helyzetet, mert a megoldásom k-ban exponenciális. Feltételezzem, hogy nincs két pont, amely egybeesne.

Ha n <= k, akkor minden ponthoz adjunk vissza egy egyenest, amin az adott pont rajta van, és készen vagyunk. Ellenkező esetben n >= k+1. Vegyünk k+1 db pontot. A skatulyelv alapján a k+1 db pontot (mint elemet) és a k db keresett egyenest (mint skatulyát) tekintve van közöttük két olyan pont, és egy keresett egyenes, hogy mindkét pont rajta van a keresett egyenesen. Ha tehát van k+1 db pont, akkor az általuk meghatározott (k+1)*k/2 db egyenes között van olyan, amely a keresett egyenesek egyike. Hogy melyik ez az egyenes, nem tudjuk, de nem is kell: visszalépéssel végigpróbáljuk mindet. (A buta végigpróbálások miatt olyan lassú az algoritmus.)

Tehát az (n,k) méretű problémát O(n) lépésben visszavezettük (k+1)*k/2 db (nn,k-1) méretű problémára. Itt az nn kicsit kevesebb, mint n, mert az épp megtalált egyenesen levő pontokat a további vizsgálatból kizárjuk.

A továbbiakban nem mondok újat, csak szemléltetem a k=1, k=2 és k=3 eseteket.

Nézzük, hogy k=1 esetén mit kell csinálni: veszünk 2 pontot, és az általuk meghatározott egyenesre rápakoljuk az összes többi pontot. Ha nem sikerül, meghiúsulást adunk vissza, ha sikerül, akkor a megtalált egyenest. Ha nincs 2 pont, akkor egy tetszőleges egyenest adunk vissza, amin az összes (0 vagy 1 db) pont rajta van.
Mindez O(n) lépésben megoldható.

k=2 esetén veszünk 3 pontot és az általuk meghatározott egyeneseket (legfeljebb 3 különböző egyenes). (Ha nincs 3 db pont, akkor minden ponthoz visszaadunk egy olyan egyenest, amin az adott pont rajta van.) Az összes egyenest végigpróbáljuk: egy adott egyenesre O(n) lépésben elfelejtjük azokat a pontokat, melyek rajta vannak, és a maradék pontokra, k=1 paraméterrel meghívjuk önmagunkat (további O(n) lépés). Összesen tehát O(1)+3*(O(n)+O(n))=O(n) lépés.

k=3 esetén veszünk négy pontot és az általuk meghatározott egyeneseket (legfeljebb 6 különböző egyenes). (Ha nincs 4 db pont, akkor minden ponthoz visszaadunk egy olyan egyenest, amin az adott pont rajta van.) Az összes egyenest végigpróbáljuk: egy adott egyenesre O(n) lépésben elfelejtjük azokat a pontokat, melyek rajta vannak, és a maradék pontokra k=2 paraméterrel meghívjuk önmagjunkat (további O(n) lépés). Összesen tehát O(1)+6*(O(n)+O(n))=O(n) lépés.

Nézzük kicsit pontosabban a becslést: hányszor kell végigolvasni a pontok listáját.

k=1 esetén egyszer elég végigolvasni (egy egyenesre rakjuk fel a rajta levő pontokat).

k=2 esetén legfeljebb három egyenesünk van, a listát minden egyenesre végigolvassuk egyszer (az egyenesre illeszkedő pontok törléséhez), és a maradék listára meghívjuk magunkat k=1-gyel (további 1 végigolvasás). Összesen tehát 3*(1+1)=6 végigolvasás.

k=3 esetén legfeljebb hat egyenesünk van, a listát minden egyenesre végigolvassuk egyszer (az egyenesre illeszkedő pontok törléséhez), és a maradék listára meghívjuk magunkat k=2-vel (további 6 végigolvasás).
Összesen tehát 6*(1+6)=42 végigolvasás. Az élet, a világmindenség meg minden.