LEGTÁVOLABBI PONTPÁROK PROBLÉMÁJA

Feladat: Megadott ponthalmazból kiválasztani az egymástól legtávolabb eső pontpárt.

Favágó módszer – megvizsgálni minden pontot minden ponttal ahhoz, hogy megtalálja az egymástól legtávolabb eső pontpárt – az egyik legbrutálisabb kivitelezési módja és természetesen ennek az algoritmusnak a bonyolultsága sem kedvező, ugyanis O(n²).

Ahhoz, hogy egy hatásosabb, elfogadhatóbb algoritmust tudjunk adni a feladatmegoldásra először tanulmányoznunk kell a legtávolabb eső pontpárok tulajdonságait. Feltételezzük, hogy S egy n síkbeli pontot tartalmazó halmaz és nevezzük átmérőnek azt a szakaszt, amely összeköt két legtávolabbi pontot S-ben.

Lemma: Legyen uv szakasz az S átmérője. Legyen l_u és l_v két egyenes, amelyek merőlegesek az uv szakaszra úgy, hogy l_u átmegy u-n és l_v átmegy v-n. Ekkor az S összes pontja az l_u és l_v között található.

Bizonyítás: Az általánosság kedvéért feltételezzük, hogy az uv szakasz vízszintes és az u pont a v pont bal oldalán található. Rajzoljunk egy C kört, amelynek középpontja az u és sugara az uv szakasz, ekkor az l_v szakasz a C érintője, mivel l_v merőleges uv-re. Így a C kör teljes egészében az l_v egyenes bal oldalán van. Tehát a v az u-tól legtávolabbi pont az S halmazban; az S összes pontjai a C körben találhatóak. Következik, hogy az S összes pontjai az l_v egyenes bal oldalán találhatóak. Hasonlóan igazolhatjuk, hogy az S összes pontjai az l_u egyenes jobb oldalán találhatóak. Így tehát az S halmaz összes pontjai az l_u és l_v egyenesek között helyezkednek el.

Tétel. Legyen uv szakasz az S halmaz átmérője, ekkor az u és v pontok a konvex burkoló csúcsai.

Legyen u és v a konvex burkoló két csúcsa. Az u és v csúcsokat ellentétes, egymással szembeni párnak nevezzük, ha tudunk rajzolni két párhuzamos érintőt, tartóegyenest a konvex burkolóhoz – az l_u és l_v egyeneseket úgy, hogy l_u átmegy u-n és l_v átmegy v-n és a konvex burkoló teljes egészében az l_u és l_v közé esik.

Tétel. Legyen uv szakasz az S halmaz átmérője, ekkor u és v ún. egymással szembeni, ellentétes párok.

Bizonyítás. Az előző tétel alapján az u és v a konvex burkoló csúcsai. A Lemma alapján megrajzolhatunk két párhuzamos l_u és l_v egyenest úgy, hogy l_u átmenjen u-n és l_v átmenjen v-n és az összes S-beli pont e két egyenes közt legyen. E két egyenes közti rész nyilvánvalóan egy konvex halmaz. Tehát az S konvex burkolója a legkisebb konvex halmaz, amelyik tartalmazza az S összes pontjait. Például a konvex burkoló benne van az összes konvex halmazban tartalmazva az S összes pontjait, tehát a konvex burkoló az l_u és l_v egyenesek között található.

A Lemma és tételei szerint ahhoz, hogy megkapjuk a legtávolabbi pontpárt az S síkbeli pontok halmazából, elég, ha megtaláljuk a konvex burkoló két legtávolabbi pontját. Még pontosabban csak az ellentétes, egymással szembeni pontok vizsgálatára van szükségünk.

Ezáltal nagyon leegyszerűsödik a feladatunk a következő formára: adott a P konvex sokszög u csúcsa és meg kell keresni azokat a pontokat, amelyek képezhetik az u csúcs szemben lévő párját.

E probléma megoldásához feltételezzük, hogy a P sokszög csúcsai az óra járásával ellentétes sorrendbe vannak megadva:{u₁ , u₂,..., u_n}. Az egyszerűség kedvéért mondjuk úgy, hogy a P sokszög u_i csúcsa a legtávolabbi az u_k1-u_k él széleitől, ha u_i a P sokszög legtávolabbi csúcsa attól az egyenestől, amelyen az u_k-1u_k szakasz elhelyezkedik.

Lemma. Legyen u_k-1u_k szakasz a P sokszög egy éle. Bejárjuk a P csúcsait az óra járásával ellentétes irányba, kezdve az u_k csúcstól. Legyen u_i az első legtávolabbi csúcs az u_k-1u_k éltől. Ekkor egyetlen u_k és u_i közti csúcs sem képezhet ellentétes pontpárt az u_k-val.

Bizonyítás. Általánosan feltételezzük, hogy az u_k-1u_k és vízszintes és az u_k csúcs az u_k-1 csúcs jobb oldalán van. Vegyük észre, hogy a P sokszög bármely u_i csúcsára az u_iu_i+1 él és az Ox tengely által bezárt szög 0 és 2P között változik. Legyen a az u_ku_k+1 él és az Ox tengely által bezárt szög. Feltételezzük, hogy a₁(a₂) az u_i-1u_i (u_iu_i+1) szakaszok és az Ox tengely által bezárt szög. Mivel P konvex következik, hogy a₁ kisebb vagy egyenlő, mint a₂ .

Könnyű belátni, hogy az u_i csúcs legtávolabbi ellentétes párja az u_k csúcsnak akkor és csakis akkor, ha az [a₁,a₂] intervallum tartalmaz egy p_i és p_i+a közti szöget.. Legyen u_j és u_k egy u_i közti csúcs (u_j<>u_k, u_j<>u_i). Ekkor az u_j nem legtávolabbi pont az u_k-1u_k szakasztól. Tehát az u_ju_j+1 él és az Ox tengely által bezárt szög, illetve az u_j-1u_j él és az Ox tengely által bezárt szög szigorúan kisebb, mint P, azaz az uj csúcs nem képezi az u_k ellentétes párját.

Lemma. Legyen u_k-1u_k szakasz a P egy éle. Bejárjuk a P csúcsait az órajárásával ellentétes irányban az u_k csúccsal kezdődően. Legyen u_r az utolsó legtávolabbi csúcspont az u_k-1u_k éltől. Ekkor egyetlen u_r és u_r-1 közti csúcspont sem lehet az u_k-1 csúcs ellentétes párja.

Bizonyítás. Hasonló az előző lemma bizonyításához.

Most már világos hogyan találjuk meg a P konvex sokszög összes ellentétes pontpárját: indulva egy u_k-1u_k éltől bejárjuk a P csúcsait az óra járásával ellentétes irányba mindaddig amíg el nem érjük az u_k-1u_k éltől legtávolabb eső u_i csúcsot. A bebizonyított lemma alapján az u_i csúcs az első olyan csúcsa a P-nek, amelyik az u_k csúcs ellentettpárja. Ezután folytatjuk a csúcsok bejárását mindaddig amíg megtaláljuk azt az u_r, amelyik az u_ku_k+1 éltől való legutolsó legtávolabbi csúcs. Az utolsó lemma alapján u_r a legutolsó csúcs, amelyik ellentétes párjka az u_k csúcsnak. Most egy csúcs ellentétes párja lehet az u_k csúcsnak akkor és csakis akkor, ha az u_i és u_r csúcsok között található. Továbbá, mivel feltételezzük, hogy nincs olyan 3 pontja a P sokszögnek, ami kollineáris következik, hogy van legalább 2 legtávolabbi pont a sokszög egyik élétől.

Algoritmus ELLENTÉTES-PÁROK:

Bemenet: a P={u(1),...,u(n)} konvex sokszög rendezve a csúcsai szerint az óra járásával ellentétes módon.

Eredmény: a P összes ellentétes párja.

BEGIN

1. indulva az {u(0),u(1)} élből, ahol az u₀ legyen az u_m csúcs. k=1, i=2.

2. Amíg u(i) nem az {u(k-1),u(k)}-tól a legtávolabbi csúcs: i=i+1

3. {ebben a pontban u(i) az {u(k-1),u(k)} éltől a legtávolabbi csúcs}.
Amíg u(i) nem az {u(k),u(k+1)} éltől legtávolabbi csúcs
KIIR([u(k),u(i)]) ellentétes pár.
i=i+1

4. {ebben a pontban u(i) az első {u(k),u(k+1)} eltől legtávolabb eső csúcs. Ellenőrízzük, hogy az u(i) az utolsó legtávolabb eső csúcs-e az {u(k),u(k+1)} éltől}.
Ha u(i+1) szintén egy legtávolabb eső csúcs {u(k),u(k+1)} éltől, akkor
KIIR[u(k),u(i)], [u(k+1),u(i)] ellentétes párok
i=i+1

5. {Most az u(i) az utolsó olyan csúcs kell legyen, amelyik ellentétes párja lehet az u(k)-nak.} KIIR[u(k),u(i)] ellentétes pár.

6. Ha k<m akkor k=k+1
vissza a 3. lépéshez.

END

Az i=i+1 beszúrás az algoritmusba “(mod m)” kellene legyen, azaz, ha i=m akkor i+1=1. Figyeljük, meg, hogy a távolság az u_i csúcs és az u_k-1u_k tartóegyenese között megfelelő az u_iu_k-1u_k háromszög területéhez, ezért az u_i csúcspont a legtávolabbi az u_k-1u_k éltől, akkor és csakis akkor, ha ennek a háromszögnek a területe nem kisebb az u_i-1u_k-1u_k valamint az u_i+1u_k-1u_k háromszögek területénél.

Egy intuitív leírása a fenti algoritmusnak az, hogy két párhuzamos egyenest használunk, ami közrefogja a P konvex sokszöget, amiután elforgatjuk a két egyenest a sokszög határánál, úgy, hogy egyforma távolságra maradjanak és ugyanakkor párhuzamosak is legyenek. A forgatás közben megjegyzünk minden olyan csúcspont párt, ami egy adott pillanatban a két egyenesre kerül.

Elemezzük az algoritmust: Használjunk két mutatót k-t és i-t. Egy adott időpontban legalább egyik mutatóval továbblépünk. Mivel k 1-től m-ig halad és az i bejárja a P sokszöget, legtöbbször kétszer (az i megáll az utolsó legtávolabbi csúcsnál az u_mu₁ éltől), arra a következtetésre jutunk, hogy az algoritmus bonyolultsága legalább O(m).

Egy további javítást tudunk végezni az algoritmusban. Ha észrevesszük, hogy amikor az i mutató eléri az u_m utolsó csúcspontot, akkor minden ellentétes pontpárt már megkaptunk.

Valójában ha az i mutatóval az u_m-ről az u₁ -re lépünk akkor azt vesszük figyelembe, hogy az u₁ is alkothat ellentétes pontpárokat a sokszög valamennyi csúcsával, de valójában minden ilyen csúcspontot már megkaptunk, amikor a k mutatóval az u₁-ről az u₂-re léptünk, de mivel ez nem befolyásolja a bonyolultságot nem tárgyaljuk részletesen.

Az algoritmus:

Bemenet: n pontot tartalmazó S síkbeli halmaz.

Eredmény: a legtávolabbi pontpár.

BEGIN

1. S konvex burkolójának a meghatározása: CH(s)

2. Meghívjuk az ellentétes párok algoritmust a CH(S)-re

3. A 2. lépés eredményéből meghatározni azt a pontpárt, amelyek között a legnagyobb a távolság.

END

Az algoritmus bonyolultsága: O(nlogn).