---

Jeg har en stribe koordinater. Jeg vil gerne finde den mindste cirkel
der indeholder en variabel del af punkterne. Der kan være overlap, så
to eller flere punkter har samme koordinat. I så fald tæller de alle
med.

Den simple måde er at starte med et af punkterne, finde en
omskrivende cirkel, der indeholder det nærmeste punkt, tilføje det
nærmeste punkt der endnu ikke er en del af cirklen, osv. indtil jeg
når til den andel der nu skal til. Dette skal så gentages for alle
punkterne. Det vil føre til et korrekt resultat, men det vil givetvis
komme til at tage en del tid, når antallet af punkter når over en vis
størrelse.

Kan man optimere det på en eller anden måde, så man slipper for at
skulle slave igennem samtlige kombinationer? Selv med de åbenlyse
optimeringer, hvor man husker den hidtil mindste pomskrivning, og
arbejder sig udad fra medianpunktet, med afbrydelse når radius bliver
større end bedste score, bliver det stadig til en rimelig kompleks
opgave.

--
/Wegge

Leder efter redundant peering af dk.*,linux.debian.*

---

Den 30/08/11 20.38, Anders Wegge Keller skrev:
>
> Jeg har en stribe koordinater. Jeg vil gerne finde den mindste cirkel
> der indeholder en variabel del af punkterne. Der kan være overlap, så
> to eller flere punkter har samme koordinat. I så fald tæller de alle
> med.
>
> Den simple måde er at starte med et af punkterne, finde en
> omskrivende cirkel, der indeholder det nærmeste punkt, tilføje det
> nærmeste punkt der endnu ikke er en del af cirklen, osv. indtil jeg
> når til den andel der nu skal til. Dette skal så gentages for alle
> punkterne. Det vil føre til et korrekt resultat, men det vil givetvis
> komme til at tage en del tid, når antallet af punkter når over en vis
> størrelse.
>
> Kan man optimere det på en eller anden måde, så man slipper for at
> skulle slave igennem samtlige kombinationer? Selv med de åbenlyse
> optimeringer, hvor man husker den hidtil mindste pomskrivning, og
> arbejder sig udad fra medianpunktet, med afbrydelse når radius bliver
> større end bedste score, bliver det stadig til en rimelig kompleks
> opgave.

Du skal finde de to punkter, der ligger længst fra hinanden. Det kan nok
ikke gøres bedre end O(n^2).

Mvh. Lars

---

Lars Kongshøj <lars_kongshoj@hotmail.com> writes:

> Den 30/08/11 20.38, Anders Wegge Keller skrev:
> >
> > Jeg har en stribe koordinater. Jeg vil gerne finde den mindste cirkel
> > der indeholder en variabel del af punkterne. Der kan være overlap, så
> > to eller flere punkter har samme koordinat. I så fald tæller de alle
> > med.
> >
> > Den simple måde er at starte med et af punkterne, finde en
> > omskrivende cirkel, der indeholder det nærmeste punkt, tilføje det
> > nærmeste punkt der endnu ikke er en del af cirklen, osv. indtil jeg
> > når til den andel der nu skal til. Dette skal så gentages for alle
> > punkterne. Det vil føre til et korrekt resultat, men det vil givetvis
> > komme til at tage en del tid, når antallet af punkter når over en vis
> > størrelse.
> >
> > Kan man optimere det på en eller anden måde, så man slipper for at
> > skulle slave igennem samtlige kombinationer? Selv med de åbenlyse
> > optimeringer, hvor man husker den hidtil mindste pomskrivning, og
> > arbejder sig udad fra medianpunktet, med afbrydelse når radius bliver
> > større end bedste score, bliver det stadig til en rimelig kompleks
> > opgave.
>
> Du skal finde de to punkter, der ligger længst fra hinanden. Det kan
> nok ikke gøres bedre end O(n^2).

Hvordan hjælper det mig lige til at finde de 90% af punkterne der
ligger tættest på hinanden?

Jeg syunes selv jeg sidder og ser på noget i retning af O(n^3), når
jeg skal finde et udsnit af mængden.

--
/Wegge

Leder efter redundant peering af dk.*,linux.debian.*

---

Den 30/08/11 21.36, Anders Wegge Keller skrev:
> Lars Kongshøj<lars_kongshoj@hotmail.com> writes:
>
>> Den 30/08/11 20.38, Anders Wegge Keller skrev:
>>>
>>> Jeg har en stribe koordinater. Jeg vil gerne finde den mindste cirkel
>>> der indeholder en variabel del af punkterne. Der kan være overlap, så
>>> to eller flere punkter har samme koordinat. I så fald tæller de alle
>>> med.
>>>
>>> Den simple måde er at starte med et af punkterne, finde en
>>> omskrivende cirkel, der indeholder det nærmeste punkt, tilføje det
>>> nærmeste punkt der endnu ikke er en del af cirklen, osv. indtil jeg
>>> når til den andel der nu skal til. Dette skal så gentages for alle
>>> punkterne. Det vil føre til et korrekt resultat, men det vil givetvis
>>> komme til at tage en del tid, når antallet af punkter når over en vis
>>> størrelse.
>>>
>>> Kan man optimere det på en eller anden måde, så man slipper for at
>>> skulle slave igennem samtlige kombinationer? Selv med de åbenlyse
>>> optimeringer, hvor man husker den hidtil mindste pomskrivning, og
>>> arbejder sig udad fra medianpunktet, med afbrydelse når radius bliver
>>> større end bedste score, bliver det stadig til en rimelig kompleks
>>> opgave.
>>
>> Du skal finde de to punkter, der ligger længst fra hinanden. Det kan
>> nok ikke gøres bedre end O(n^2).
>
> Hvordan hjælper det mig lige til at finde de 90% af punkterne der
> ligger tættest på hinanden?
>
> Jeg syunes selv jeg sidder og ser på noget i retning af O(n^3), når
> jeg skal finde et udsnit af mængden.

Du har ret, jeg fik læst din beskrivelse for hurtigt.

Mvh. Lars

---

Anders Wegge Keller <wegge@wegge.dk> writes:

> Jeg har en stribe koordinater. Jeg vil gerne finde den mindste cirkel
> der indeholder en variabel del af punkterne. Der kan være overlap, så
> to eller flere punkter har samme koordinat. I så fald tæller de alle
> med.

Der findes en lineærtidsalgoritme til at finde den mindste cirkel
omkring et antal punkter. Garanteret lineær tid kræver en lidt kompleks
algoritme, men hvsi du kan nøjes med gennemsnitlig lineær tid, er der en
meget simpel algoritme.

Welzls algoritme udnytter, at den mindste cirkel omkring en punktmængde
enten rører to punkter, som så definerer en diameter i cirklen, eller
mindst tre punkter, hvor tre vilkårlige af disse er nok til at definere
cirklen. Den mindste cirkel omkring punktmængden kan altså beskrives
med tre punkter i mængden. Og hvis der er N punkter i mængden, er
sandsynligheden for, at et tilfældigt udvalgt punkt er en af disse tre,
3/N.

Algoritmen er beskrevet som en rekursiv funktion, der har to parametre:

- points er punktmængden.

- used er en mængde af op til tre punkter, der i den nuværende hypotese
indgår i de tre punkter, der definerer cirklen.

Resultatet er den mindste cirkel

I pseudokode er funktionen sådan her:

minCircle(points,used)
if |points| + |used| <= 3 /* hvis der er højest tre punkter i alt */
then return findCircle(points U used) /* U er foreningsmængde */
else
p = pickRandom(points); /* vælg tilfældigt punkt */
newpoints = points \ {p}; /* fjern p fra mængden */
circle = minCircle(newpoints, used) /* prøv uden punktet */
if p is inside circle /* høj sandsynlighed */
then return circle;
else return minCircle(newpoints, used U {p}); /* tilføj p til used */

Funktionen findCircle finder mindste cirkel omkring de op til tre
punkter, der er givet som argument. Det kan enten være en cirkel med to
af punkterne som diameter eller en cirkel, der rører alle tre punkter.
Det er simpel geometri, så det overlader jeg til dig at finde ud af.

En tidsanalyse viser, at hvis p vælges helt tilfældigt, så er den
forventede (gennemsnitlige) tid lineær i antallet af punkter i points.

   Torben

---

torbenm@diku.dk (Torben Ægidius Mogensen) writes:

> Anders Wegge Keller <wegge@wegge.dk> writes:
>
> > Jeg har en stribe koordinater. Jeg vil gerne finde den mindste cirkel
> > der indeholder en variabel del af punkterne. Der kan være overlap, så
> > to eller flere punkter har samme koordinat. I så fald tæller de alle
> > med.

> Der findes en lineærtidsalgoritme til at finde den mindste cirkel
> omkring et antal punkter. Garanteret lineær tid kræver en lidt kompleks
> algoritme, men hvsi du kan nøjes med gennemsnitlig lineær tid, er der en
> meget simpel algoritme.

Det var en snedig algoritme. Den burde kunne bringe min samlede
kompleksitet ned på O(N^2 log N).

--
/Wegge

Leder efter redundant peering af dk.*,linux.debian.*