[Alg] Grootste afstand tussen 2 punten

[Zoijar]

Ik was even in een boek aan het bladeren, en merkte toen iets op dat van toepassing was op dit oude, gesloten topic.

HIGHGuY in "grootste afstand tussen 2 punten uit wil..."

Het topic ging over de twee punten met maximale afstand te vinden uit een verzameling, en de complexiteit van dit probleem. Highguy dacht een O(n) oplossing gevonden te hebben, en de algemen mening (?) was dat O(n log n) waarschijnlijk minimaal was.

Nu las ik het volgende:

"There is an improved algorithm [to solve the closest points problem] in O(n log n) time and works by avoiding the computation of all distances [divide and conquer]. There is also an algorithm that is expected to take O(n) time. These last two algorithms use subtle observations to provide faster results and are beyond the scope of this text."

Het probleem heet dus het "closest points" probleem. Het probleem van highguy is hier uiteraard equivalent aan: je kan simpel weg de afstand tussen punten definieren als 1/d, waar d de echte afstand is. Ik weet niet precies welk algoritme er bedoeld wordt, maar er blijkt dus een "expected linear time" algoritme te bestaan. Met google en 'closest points problem' moet het verder wel lukken.

[ Voor 3% gewijzigd door Zoijar op 11-10-2005 21:32 ]

[.oisyn]

Interessant, kun je in 't kort vertellen wat dat algoritme doet?
Ze zullen wel een bepaalde heuristiek gebruiken. Ik vraag me trouwens af of je 1/d argument opgaat bij een dergelijk algoritme.

[Confusion]

Als iemand schrijft dat er een algoritme is 'which is expected to take O(n) time', dan kan je concluderen dat de auteur het algoritme niet heeft getest, niet heeft bestudeerd of het algoritme inderdaad O(n) tijd nodig heeft en waarschijnlijk zelfs het algoritme nooit gezien heeft.

[Zoijar]

Ik zoek het morgen even na wat het precies is...

Confusion schreef op dinsdag 11 oktober 2005 @ 22:01:
Als iemand schrijft dat er een algoritme is 'which is expected to take O(n) time', dan kan je concluderen dat de auteur het algoritme niet heeft getest, niet heeft bestudeerd of het algoritme inderdaad O(n) tijd nodig heeft en waarschijnlijk zelfs het algoritme nooit gezien heeft.

Nee, dat is het niet 'expected' is een algoritme technische term als in de verwachtingswaarde/expectation. Als je input random verdeeld is, dan is de verwachtingswaarde van je runtime lineair / O(n). Ook wordt er wel "average case" mee bedoeld, ie. met normale, gemiddelde input dan zal je runtime (amortized) lineair zijn. Het betekent niet dat de auteur wel verwacht dat het lineair zou kunnen zijn Eventueel zou het misschien nog kunnen zijn dat men algemeen denkt dat het lineair is, maar dat niet kan bewijzen (zoals bv. expected non-polynomial voor npc)... maar dat lijkt me heel sterk. Hoogst waarschijnlijk is het het bovenste.

.oisyn schreef op dinsdag 11 oktober 2005 @ 21:53:
Ik vraag me trouwens af of je 1/d argument opgaat bij een dergelijk algoritme.

Zou misschien kunnen dat het niet zo is als er iets gedaan wordt met planaire grafen en algoritmes daarop oid. Hoewel, de 1/d metriek is dacht ik gewoon een metriek dus dan zou het alsnog moeten gaan op een metrische ruimte. Iets te lang geleden....

[ Voor 19% gewijzigd door Zoijar op 11-10-2005 22:57 ]

[Confusion]

Zoijar schreef op dinsdag 11 oktober 2005 @ 22:50:
Nee, dat is het niet 'expected' is een algoritme technische term als in de verwachtingswaarde/expectation.

Hmmm, zo las ik die zin niet. Dat geldt toch altijd voor een orde aanduiding? Ik dacht dat bijvoorbeeld O(n log(n)) algoritmen voor bijzondere gevallen O(n) zijn en dat O(n log(n)) altijd de verwachtingswaarde is. Waarom zou hij dat dan nu opeens expliciet melden? Sterker nog: als O(n) de verwachtingswaarde is, dan impliceert dat dat het voor bijzondere gevallen beter dan O(n) zou presteren. Daar geloof ik helemaal niets van .

[Zoijar]

Confusion schreef op dinsdag 11 oktober 2005 @ 23:07:
Hmmm, zo las ik die zin niet. Dat geldt toch altijd voor een orde aanduiding? Ik dacht dat bijvoorbeeld O(n log(n)) algoritmen voor bijzondere gevallen O(n) zijn en dat O(n log(n)) altijd de verwachtingswaarde is. Waarom zou hij dat dan nu opeens expliciet melden? Sterker nog: als O(n) de verwachtingswaarde is, dan impliceert dat dat het voor bijzondere gevallen beter dan O(n) zou presteren. Daar geloof ik helemaal niets van .

Nee, big O is in principe de worst-case tijd als er niets gegeven wordt. Er zijn verschillende letter aanduidingen voor verschillende dingen, maar worst-case is het meest standaard (zo ook best-case, average-case, en amortized/gemiddeld dan duurt het soms lang maar dan ook vaak kort, dus gemiddeld kort. Denk aan het resizen van een vector bij insertion)

In het geval van expected O(n) dan kan het ook soms wel eens O(n^2) zijn bij bepaalde input. Je zou eigenlijk een variantie moeten hebben dan om aan te geven hoe vaak het goed gaat en hoe vaak het slecht gaat. Dit soort aanduidingen zijn er ook wel. Het hoeft niet beter te gaan dan O(n), maar er is natuurlijk wel een praktisch verschil tussen O(100*n) en O(2*n) daar die in de theorie gelijk zijn. Dat is de 'constant factor'.

(leuk voorbeeld is altijd random-sort. Om een lijst te sorteren pak je gewoon random elementen, en je kijkt of die op volgorde staan. Dit is een O(n) operatie. Je kan bij het pakken meteen al kijken of de volgorde goed is, ie. oplopend. Wat is de complexiteit van dit algoritme? Hebben we een lineair sorteer algoritme? Worst case? Best case? Als je toevallig meteen goed pakt is het O(n). Als je een vast aantal constante pogingen nodig hebt is het O(c*n) = O(n). Je kan alleen berekenen wat het verwachtte aantal pogingen is gegeven n. De complexiteit van dit algoritme kan je dan alleen aanduiden met expected/average O(n * n!) en best-case dus O(n), worst-case O(inf) ... iets dat worst-case O(inf) is is niet echt een fijn algoritme)

[ Voor 23% gewijzigd door Zoijar op 11-10-2005 23:31 ]

[matthijsln]

Zoijar schreef op dinsdag 11 oktober 2005 @ 21:30:
Het probleem heet dus het "closest points" probleem. Het probleem van highguy is hier uiteraard equivalent aan: je kan simpel weg de afstand tussen punten definieren als 1/d, waar d de echte afstand is. Ik weet niet precies welk algoritme er bedoeld wordt, maar er blijkt dus een "expected linear time" algoritme te bestaan. Met google en 'closest points problem' moet het verder wel lukken.

Je kan natuurlijk niet zomaar een closest-pair algoritme met een simpele 1/d ombouwen naar een farthest-pair algoritme, omdat zo'n algoritme meestal een divide-and-conquer algoritme is; dwz dat het juist vermijdt om alle afstanden tussen alle punten te berekenen (brute-force). Heb je eenmaal alle afstanden tussen alle punten berekend dan kan je inderdaad net als de kleinste afstand ook wel de grootste afstand bepalen, maar snel is het niet

[MSteverink]

Nu is mijn wiskundige kennis wat afgezakt, en ben ik ook nog eens niet in de omstandigheden dat ik een en ander kan proberen. Maar:
uitgaande van een Euclidische afstand;
uitgaande van m punten in n dimensies;

definieren we een matrix X, met elementen x_mn, die de co-ordinaten van de punten bevatten.

Als we nu een singuliere waarden decompositie doen op X, resulterend in K, LABDA en L, dan heeft (K LABDA L) eenzelfde structuur als X, met dien verstande dat (K LABDA L) orthogonaal is, en de meeste variantie heeft op de eerste dimensie.
De punten met de grootste afstand zijn die punten met respectievelijk de hoogste en de laagste coordinaat op de eerste dimensie.

--

Om 13:58 begon MSteverink zelf ernstig te twijfelen aan bovenstaande. De gevonden afstand zal tot de grootste behoren, maar of het ook de allergrootste is?

[ Voor 15% gewijzigd door MSteverink op 12-10-2005 14:00 ]

[H!GHGuY]

interessant... ik hou me ter beschikking.

@MSteverinck: daar heb'k nou nix van verstaan
misschien dat'k eens m'n oude cursus wiskunde bovenhaal

wat mijn topic betreft: Ik heb aan m'n stagebedrijf gevraagd of ik m'n algo mocht "publiceren" en ze gingen et uitzoeken.

[Verwijderd]

Als ik het nog goed weet is:

- O(f(n)): worst-case looptijd ter orde van f(n);
- Ω(f(n)): best-case looptijd ter orde van f(n);
- Θ(f(n)): gemiddelde (verwachte) looptijd ter orde van f(n).

(Maar misschien heb ik de omega en theta verkeerd om )

[MrBucket]

Verwijderd schreef op woensdag 12 oktober 2005 @ 10:59:
Als ik het nog goed weet is:

- O(f(n)): worst-case looptijd ter orde van f(n);
- Ω(f(n)): best-case looptijd ter orde van f(n);
- Θ(f(n)): gemiddelde (verwachte) looptijd ter orde van f(n).

(Maar misschien heb ik de omega en theta verkeerd om )

Ω en Θ heb je niet omgewisseld, zo klopt het

Maar: Θ is niet de gemiddelde of verwachte looptijd. Het betekent dat de looptijd zowel aan de bovenkant als aan de onderkant wordt begrensd door een orde f(n) functie. M.a.w.: de looptijd is zowel O(f(n)) als Ω(f(n)). Of in woorden: er kan gegarandeerd worden dat er voor een inputgrootte n het algoritme maximaal c * f(n) tijd kost, maar er kan ook gegarandeerd worden dat het minimaal b * f(n) tijd kost (waarbij b < c).

[Verwijderd]

Ohja.

Gheh.

[Ivo]

Inderdaad, mag ik dan nog even verduidelijken. Omega, Theta en O-notatie kunnen allen van toepassing zijn op best, average en worst-case scenario's. Het enige wat ze zeggen is hoe een functie begrensd is. Stellen dat een algoritme worst-case O(n) is betekent dus gewoon dat dit algoritme Theta(x) is voor Theta(x) in Omega(n).

[0siris]

[Alg] Grootste afstand tussen 2 punten

_{Vergeef me mijn onkunde, maar is de grootste afstand tussen 2 punten niet gewoon oneindig}

[MrBucket]

matthijsln schreef op dinsdag 11 oktober 2005 @ 23:33:
[...]


Je kan natuurlijk niet zomaar een closest-pair algoritme met een simpele 1/d ombouwen naar een farthest-pair algoritme, omdat zo'n algoritme meestal een divide-and-conquer algoritme is; dwz dat het juist vermijdt om alle afstanden tussen alle punten te berekenen (brute-force).

Dat dacht ik dus ook...?

Althans, ik zie niet in hoe je een soort van inverse-ruimte zou kunnen maken waarin punten die normaal gesproken heel ver van elkaar af zouden liggen, nu heel dichtbij elkaar liggen, en vice versa. Misschien dat TS iets meer licht in de duisternis kan brengen?

0siris schreef op woensdag 12 oktober 2005 @ 12:28:
_{Vergeef me mijn onkunde, maar is de grootste afstand tussen 2 punten niet gewoon oneindig}

Het zij je vergeven

De vraag is eigenlijk: bepaal van een gegeven verzameling punten het paar dat de grootste onderlinge afstand heeft. Maar dat paste niet in de titel, denk ik

[ Voor 23% gewijzigd door MrBucket op 12-10-2005 12:32 ]

[Verwijderd]

HIGHGuY schreef op woensdag 12 oktober 2005 @ 10:58:
@MSteverinck: daar heb'k nou nix van verstaan
misschien dat'k eens m'n oude cursus wiskunde bovenhaal

Oei, als je met vectoren aan het rekenen bent en niet weet wat een euclidische afstand is dan lijk je toch een probleem te hebben. Dit was indertijd toch echt propadeuse werk. Een singular value decomposition was geloof ik werk voor het tweede jaar.

Maar goed wat MSteverinck volgens mij bedoeld is dat je de punten in een mx 2 matrix zet en hier een SVD op toepast. Dan krijg je drie matrices K Labda en L
Het interessanste is de matrix Labda want dat is de stretcher matrix die aangeeft hoe ver de punten worden "uitgetrokken" door de transformatie. MSteveninck zegt nu dat je door de punten met de hoogste en laagste waarde op de eerste dimensie te nemen de punten met de grootste onderlinge afstand gevonden hebt. Of dat klopt is weer een tweede Daar kan ik mij geen bewijs van herinneren. Maar sowieso vraag ik mij af of het praktisch is om het op deze manier te doen.

[ Voor 13% gewijzigd door Verwijderd op 12-10-2005 13:26 ]

[Knutselsmurf]

Verwijderd schreef op woensdag 12 oktober 2005 @ 13:13:
[...]


Oei, als je met vectoren aan het rekenen bent en niet weet wat een euclidische afstand is dan lijk je toch een probleem te hebben. Dit was indertijd toch echt propadeuse werk. Een singular value decomposition was geloof ik werk voor het tweede jaar.

Maar goed wat MSteverinck volgens mij bedoeld is dat je de punten in een mx 2 matrix zet en hier een SVD op toepast. Dan krijg je drie matrices K Labda en L
Het interessanste is de matrix Labda want dat is de stretcher matrix die aangeeft hoe ver de punten worden "uitgetrokken" door de transformatie. MSteveninck zegt nu dat je door de punten met de hoogste en laagste waarde op de eerste dimensie te nemen de punten met de grootste onderlinge afstand gevonden hebt. Of dat klopt is weer een tweede Daar kan ik mij geen bewijs van herinneren. Maar sowieso vraag ik mij af of het praktisch is om het op deze manier te doen.

Ik heb een donkerbruin vermoeden dat dit niet de meest efficiente methode is. De meest eenvoudige methode om dit op te lossen (gewoon alle puntencombinaties vergelijken) is O(n^2).

Als je dan ziet dat een vermenigvuldiging van een n*n-matrix met een vector al O(n^2) is, dan is al snel te zien dat iedere poging om dit met maxtrix-operaties op te lossen minder efficient is dan eerder genoemde methode.

[Verwijderd]

Punt is wel dat de Labda matrix alleen waarden heeft op de diagonaal. De orde van de berekening hoeft dus niet per se n^2 te zijn. Ook is het natuurlijk nergens voor nodig om de matrices K, Labda en L weer te gaan vermenigvuldigen. Je breekt de matrix juist op in stukken waarvan je weet wat ze doen.

Hoewel ik geen O(1) algoritme verwacht, is het ook niet zo dat als je een nxn matrix ziet staan je per definitie O(n^2) krijgt. Matrix notatie is niets anders dan dat, een notatie. Maar door in matrices te denken kun je verschillende zaken veel effectiever doen dan zonder dat inzicht. De implementatie van die inzichten kunnen overigens vaak gewoon row based zijn.

[ Voor 71% gewijzigd door Verwijderd op 12-10-2005 14:58 ]

[H!GHGuY]

Verwijderd schreef op woensdag 12 oktober 2005 @ 13:13:
[...]


Oei, als je met vectoren aan het rekenen bent en niet weet wat een euclidische afstand is dan lijk je toch een probleem te hebben. Dit was indertijd toch echt propadeuse werk. Een singular value decomposition was geloof ik werk voor het tweede jaar.

Maar goed wat MSteverinck volgens mij bedoeld is dat je de punten in een mx 2 matrix zet en hier een SVD op toepast. Dan krijg je drie matrices K Labda en L
Het interessanste is de matrix Labda want dat is de stretcher matrix die aangeeft hoe ver de punten worden "uitgetrokken" door de transformatie. MSteveninck zegt nu dat je door de punten met de hoogste en laagste waarde op de eerste dimensie te nemen de punten met de grootste onderlinge afstand gevonden hebt. Of dat klopt is weer een tweede Daar kan ik mij geen bewijs van herinneren. Maar sowieso vraag ik mij af of het praktisch is om het op deze manier te doen.

* H!GHGuY is belg
dus wanner wat gezien is op school zal wel niet kloppen. vectoren en euclidische afstanden ken ik natuurlijk wel, en m*2 matrices etc.

maar die single value decomposition zegt me op dit moment niet zoveel... mss moet ik er ff een boekje op nakijken

Eigenlijk is mijn algo een soort voorsortering van de punten wat altijd O(n) is.
Het reduceert de te testen punten enorm. De basisvorm houdt O(C) punten over, de vorm zonder fouten houdt O(x*n) met 0 < x < 1 en x gemiddeld zeer klein.
Dit is waarom het worst-case zonder fouten toch nog steeds O(n²) worst-case is, maar gemiddeld toch een O(n) zal zijn.

[Verwijderd]

Eigenlijk is mijn algo een soort voorsortering van de punten wat altijd O(n) is.
Het reduceert de te testen punten enorm. De basisvorm houdt O(C) punten over, de vorm zonder fouten houdt O(x*n) met 0 < x < 1 en x gemiddeld zeer klein.
Dit is waarom het worst-case zonder fouten toch nog steeds O(n²) worst-case is, maar gemiddeld toch een O(n) zal zijn.

Kijk het is vrij simpel om een hoop punten kwijt te raken. Simpel voorbeeld Je loopt 1 keer over je punten heen om de grenzen van x en y te bepalen. Je maximale afstand is dus kleiner (of gelijk) dan de afstand van de hoekpunten van dit vierkant maar groter of gelijk aan de hoogte en de breedte van dit vierkant.
Nu heb je de diagonaal van het complete vierkant nodig en het maximum van de hoogte en de breedte.
Punten die in een cirkel in het midden van dit vierkant liggen waarvan de diameter van de cirkel gelijk is aan het maximum van de hoogte en de breedte min het verschil tussen de diagonaal en dit maximum kun je daarna met zekerheid verwijderen.
(Off Topic: Dit algoritme is vrij toepasbaar mits vermeld wordt dat het bedacht is door Jan Klaasen Het kan trouwens o.a. nog verbeterd worden door elk nieuw gevonden maximale afstand direct te gebruiken in plaats van het initiele maximum van hoogte en breedte )

Vaak zal dit een flink aantal punten zijn maar soms ook helemaal geen. Zo'n optimalisatie heeft dus totaal geen invloed op de Orde van het algoritme. Je moet nog steeds n-x punten vergelijken met een algoritme van O(nlogn) of O(n^2) Dus verandert de orde niet De voorsortering maakt het echter wel sneller

Mijn grootste probleem is dat jou algoritme fouten introduceert. Misschien klein en niet relevant maar het laat de mogelijkheid open dat in bepaalde (speciaal geconstrueerde) gevallen de uitkomst niet klopt. Dat is in mijn optiek vele malen erger dan een wat trager algoritme.

Het is echter lastig praten aangezien jou algoritme "geheim" is. Het nut van het geheim houden van algoritmes ontgaat mij enigszins maar dat is een ander topic.

[MrBucket]

Nu ik de post boven mij lees: het paar punten dat het verste uit elkaar ligt moeten beide op de convex hull van de puntenverzameling liggen.

De convex hull uitrekenen van een willekeurige verzameling punten in R2 kost O(n log n) tijd, zijn de punten al gesorteerd (op een willekeurige as), dan kan dit in lineaire tijd door in een intelligente manier over de punten heen te lopen.

Gezien de convexiteit van de convex hull (goh!), zal het volgens mij niet al te moeilijk zijn om in lineaire tijd van een convex hull het paar punten te bepalen dat het verst uit elkaar ligt. Maar dat betekent nog steeds dat je bij een ongesorteerde puntenverzameling niet lager dan O(n log n) komt.

[H!GHGuY]

fouten introduceren ~ de grootte van de fout is zeer klein, en is maar in extreme gevallen aanwezig.

ik heb het op bvb een fout van 1 op een afstand van enkele 1000'en of meer...
bovendien zijn er enkele simpele truukjes om die fout drastisch kleiner te maken zonder veel verlies in snelheid. Het komt erop neer dat in zo'n geval gewoon de 2de grootste afstand of zo gevonden wordt.

geen probleem dus als je meetresultaten verwerkt (zoals ik doe)

MrBucket schreef op woensdag 12 oktober 2005 @ 16:10:
Nu ik de post boven mij lees: het paar punten dat het verste uit elkaar ligt moeten beide op de convex hull van de puntenverzameling liggen.

De convex hull uitrekenen van een willekeurige verzameling punten in R2 kost O(n log n) tijd, zijn de punten al gesorteerd (op een willekeurige as), dan kan dit in lineaire tijd door in een intelligente manier over de punten heen te lopen.

Gezien de convexiteit van de convex hull (goh!), zal het volgens mij niet al te moeilijk zijn om in lineaire tijd van een convex hull het paar punten te bepalen dat het verst uit elkaar ligt. Maar dat betekent nog steeds dat je bij een ongesorteerde puntenverzameling niet lager dan O(n log n) komt.

ik moet me eens dringend in het convex hull algo gaan verdiepen

[ Voor 50% gewijzigd door H!GHGuY op 12-10-2005 16:36 ]

[Soultaker]

MrBucket schreef op woensdag 12 oktober 2005 @ 16:10:
Gezien de convexiteit van de convex hull (goh!), zal het volgens mij niet al te moeilijk zijn om in lineaire tijd van een convex hull het paar punten te bepalen dat het verst uit elkaar ligt.

Hoe dan? Het lijkt mij nog niet triviaal namelijk.

[MrBucket]

HIGHGuY schreef op woensdag 12 oktober 2005 @ 16:29:
fouten introduceren ~ de grootte van de fout is zeer klein, en is maar in extreme gevallen aanwezig.

ik heb het op bvb een fout van 1 op een afstand van enkele 1000'en of meer...
bovendien zijn er enkele simpele truukjes om die fout drastisch kleiner te maken zonder veel verlies in snelheid. Het komt erop neer dat in zo'n geval gewoon de 2de grootste afstand of zo gevonden wordt.

geen probleem dus als je meetresultaten verwerkt (zoals ik doe)

Mja. Ik denk dat je wel moet kiezen.

Als je gaat voor een oplossing die in de praktijk snel loopt prima, maar dan hoef je je niet druk te maken om wiskundige trucjes die de theoretische tijdsgrens lager maken.

Wil je echter een theoretisch optimaal algoritme (zoals jouw rekentrucje doet vermoeden), dan is het wel een probleem dat het af en toe het verkeerde antwoord oplevert. Monte Carlo algoritmen zijn doorgaans niet interessant voor zulke eenvoudige problemen...

[Soultaker]

Zoijar schreef op dinsdag 11 oktober 2005 @ 21:30:
Het probleem heet dus het "closest points" probleem. Het probleem van highguy is hier uiteraard equivalent aan: je kan simpel weg de afstand tussen punten definieren als 1/d, waar d de echte afstand is.

We hebben het over een 'standaard' Euclidische ruimte neem ik aan, dus dan werkt zo'n truc zeker niet omdat dingen als de driehoeksongelijkheid (afstand(a,b) + afstand(b,c) >= afstand(a,c)) dan opeens niet meer opgaan.

De verst-uit-elkaar-gelegen punten vinden lijkt mij dus fundamenteel anders dan de dichts-bij-elkaar-gelegen punten vinden.

[ Voor 18% gewijzigd door Soultaker op 12-10-2005 16:45 ]

[MrBucket]

Soultaker schreef op woensdag 12 oktober 2005 @ 16:34:
[...]

Hoe dan? Het lijkt mij nog niet triviaal namelijk.

Nee, het is idd niet triviaal (daar verkeek ik me ook een beetje op), maar:

Gegeven een verzameling punten P = {p1, p2, ... pn} gesorteerd in clockwise order, die de vertices van een convex hull vormen. Stel dat je van punt p1 wil bepalen welk ander punt uit P het verst er vanaf ligt, en je loopt in clockwise order de punten p2...pn af, dan kan je volgens mij maar 2 lokale maxima vinden, d.w.z hooguit twee punten uit P waarvoor de afstand tot p1 groter is dan die van zijn directe buren. Minimaal 1, maar volgens mij maximaal 2.

Hier zou je toch wat mee moeten kunnen doen, lijkt me.

[Confusion]

Soultaker schreef op woensdag 12 oktober 2005 @ 16:39:
We hebben het over een 'standaard' Euclidische ruimte neem ik aan, dus dan werkt zo'n truc zeker niet omdat dingen als de driehoeksongelijkheid (afstand(a,b) + afstand(b,c) >= afstand(a,c)) dan opeens niet meer opgaan.

Tjah, als je een Euclidische ruimte inverteert, dan is het geen Euclidische ruimte meer: je helpt het derde postulaat naar de knoppe.

[Soultaker]

MrBucket schreef op woensdag 12 oktober 2005 @ 16:48:
Nee, het is idd niet triviaal (daar verkeek ik me ook een beetje op), maar:

Gegeven een verzameling punten P = {p1, p2, ... pn} gesorteerd in clockwise order, die de vertices van een convex hull vormen. Stel dat je van punt p1 wil bepalen welk ander punt uit P het verst er vanaf ligt, en je loopt in clockwise order de punten p2...pn af, dan kan je volgens mij maar 2 lokale maxima vinden, d.w.z hooguit twee punten uit P waarvoor de afstand tot p1 groter is dan die van zijn directe buren. Minimaal 1, maar volgens mij maximaal 2.

Ja, ik zat ook al te denken: als je begint bij P en je loopt rond dan wordt de afstand eerst steeds groter en daarna steeds kleiner; volgens mij kan er vanwege de convexiteit geen 'deuk' inzitten. Er is dus maar één optimum en dat betekent dat je met een binary search de afstand van punt P tot het verste punt Q in O(log N) kunt bepalen. Als je dus simpelweg vanuit elk punt afzonderlijk kijkt kom je op O(N log N).

Overigens kunnen er een willekeurig aantal punten op dezelfde (maximale) afstand van P liggen: denk maar aan de situatie waarin de punten op een cirkelboog liggen waarvan P het centrum is.

Hier zou je toch wat mee moeten kunnen doen, lijkt me.

Ja, volgens mij moet het nog wel wat slimmer kunnen inderdaad.

Confusion schreef op woensdag 12 oktober 2005 @ 16:50:
Tjah, als je een Euclidische ruimte inverteert, dan is het geen Euclidische ruimte meer: je helpt het derde postulaat naar de knoppe.

Inderdaad, en dan werken alle algoritmen die uitgaan van die eigenschappen opeens niet meer.

[ Voor 52% gewijzigd door Soultaker op 12-10-2005 16:56 ]

[MrBucket]

Soultaker schreef op woensdag 12 oktober 2005 @ 16:54:
[...]

Ja, ik zat ook al te denken: als je begint bij P en je loopt rond dan wordt de afstand eerst steeds groter en daarna steeds kleiner; volgens mij kan er vanwege de convexiteit geen 'deuk' inzitten. Er is dus maar één optimum

Bijna goed Het kunnen er twee zijn.

Teken maar eens een ovaal die breder is dan dat hij hoog is. Stel dat punt p1 op 12 uur ligt, dan heb je twee punten die de grootste afstand vormen, deze liggen dan ong. op 4 en 8 uur. 6 uur vormt dan een deuk

en dat betekent dat je met een binary search de afstand van punt P tot het verste punt Q in O(log N) kunt bepalen. Als je dus simpelweg vanuit elk punt afzonderlijk kijkt kom je op O(N log N).

Nou, ik zat meer zo te denken: voor een enkel punt weet je in lineaire tijd met welke het de grootste afstand vormt. Voor een lineair aantal punten zou je dan wat slims moeten kunnen doen met bovenstaande eigenschap. Zoiets als: "als ik de punten afloop op zoek naar het eindpunt met de maximale afstand tot mijn beginpunt, maar deze afstand is kleiner als de afstand tot het vorige eindpunt, dan moet ik ook meteen een volgend beginpunt kiezen.".

Iets in die richting, iig.

[ Voor 24% gewijzigd door MrBucket op 12-10-2005 17:05 ]

[Soultaker]

edit:
Ah, gegeven een convex hull kan het inderdaad in O(N) tijd, als mijn aanname dat er maar één optimum is klopt. Je neemt een beginpunt P en vindt daarbij een punt Q dat er het verst van afligt (dat kan in O(N) maar desnoods in O(log N)). Nu heb je dus een ondergrens voor de totale afstand.

Als je nu punt P een plek opschuift, dan ligt Q ofwel op of voor het optimum. Het optimum kun je dus vinden door Q door te schuiven tot het weer optimaal is. Dit herhaal je tot je alle punten P gehad hebt; Q is daarbij ook precies één keer rondgegaan. Dat is dus een O(N) operatie.

Indien de punten gesorteerd worden aangeleverd is er dus een O(N) algoritme; zoniet, dan in ieder geval een O(N log N) algoritme (omdat je ze daarin kunt sorteren) en eerlijk gezegd lijkt het me sterk dat het efficiënter kan.

MrBucket schreef op woensdag 12 oktober 2005 @ 17:00:
Bijna goed Het kunnen er twee zijn.

Teken maar eens een ovaal die breder is dan dat hij hoog is. Stel dat punt p1 op 12 uur ligt, dan heb je twee punten die de grootste afstand vormen, deze liggen dan ong. op 4 en 8 uur. 6 uur vormt dan een deuk

Argh, inderdaad. Bah.

Er zijn trouwens een heleboel punten die het verst liggen maar niet naast elkaar liggen. Neem bijvoorbeeld een cirkelboog met P als centrum en teken op de cirkelboog een aantal punten; al deze punten liggen op dezelfde (optimale) afstand van P. Vervolgens zet je midden tussen elk paar van deze punten (dus bínnen de cirkel) een punt; deze punten liggen dichterbij maar nog wel op de convex hull; je hebt zo dus met N punten N/2 optima.

Plaatje erbij:

De blauwe punten zijn optima; de rode niet maar liggen wel op de convex hull (de blauwe lijnen).

[ Voor 45% gewijzigd door Soultaker op 12-10-2005 17:20 ]

[MrBucket]

Soultaker schreef op woensdag 12 oktober 2005 @ 17:01:
edit:
Ah, gegeven een convex hull kan het inderdaad in O(N) tijd, als mijn aanname dat er maar één optimum is klopt. Je neemt een beginpunt P en vindt daarbij een punt Q dat er het verst van afligt (dat kan in O(N) maar desnoods in O(log N)). Nu heb je dus een ondergrens voor de totale afstand.

Als je nu punt P een plek opschuift, dan ligt Q ofwel op of voor het optimum. Het optimum kun je dus vinden door Q door te schuiven tot het weer optimaal is. Dit herhaal je tot je alle punten P gehad hebt; Q is daarbij ook precies één keer rondgegaan. Dat is dus een O(N) operatie.

Indien de punten gesorteerd worden aangeleverd is er dus een O(N) algoritme; zoniet, dan in ieder geval een O(N log N) algoritme (omdat je ze daarin kunt sorteren) en eerlijk gezegd lijkt het me sterk dat het efficiënter kan.


[...]

Argh, inderdaad. Bah.

Er zijn trouwens een heleboel punten die het verst liggen maar niet naast elkaar liggen. Neem bijvoorbeeld een cirkelboog met P als centrum en teken op de cirkelboog een aantal punten; al deze punten liggen op dezelfde (optimale) afstand van P. Vervolgens zet je midden tussen elk paar van deze punten (dus bínnen de cirkel) een punt; deze punten liggen dichterbij maar nog wel op de convex hull; je hebt zo dus met N punten N/2 optima.

Grrmbl.

Ik voelde al nattigheid toen ik erachter kwam dat er niet 1, maar 2 optima gevonden konden worden. Meestal blijft het dan ook niet bij 2...

[Zoijar]

Ja, die 1/d conclusie was idd iets te voorbarig. Het probleem is daar idd de driehoeks ongelijkheid. Jammer.

In ieder geval blijkt het furthest-/farthest-pair/diameter probleem niet fundamenteel moeilijker dan het closest pair probleem. Er is al heel veel onderzoek naar gedaan trouwens. Veel focus ligt op dimensie 4+, want 2d of 3d zijn er verschillende snelle oplossingen (O(n log n) exact van wat ik zie, en O(n) benadering) Maar ook over 2d en 3d zijn verschillende papers te vinden. Zoek termen "furthest pair" "farthest pair" "diameter problem" "closest pair". Het standaard algoritme is een line-sweep algoritme.

Oa. vond ik bv nog deze paper: http://theory.lcs.mit.edu/~indyk/metrics99.ps die een O(n) benadering voor furthest pair geeft.

Je moet zelf maar nazoeken of jouw algoritme al beschreven is (ik heb nu wel genoeg literatuur onderzoek gedaan, niet m'n favoriet... ), en of het iets nieuws toevoegt. Wie weet... hoewel ik het persoonlijk betwijfel als ik zo kijk naar het volume van papers over dit onderwerp.

[H!GHGuY]

ik ben nu ghostscript aan het downen, het gaat maar wat traag... daarna bekijk ik die ps file wel even

Dat document toont andere problemen. Maar ik heb er niet echt iets in gevonden wat lijkt op wat ik doe.

[ Voor 35% gewijzigd door H!GHGuY op 12-10-2005 19:28 ]