Linus Källberg försvarar sin doktorsavhandling i datavetenskap

Disputationer och licentiatseminarier

Datum: 2020-01-10
Tid: 13.15
Plats: sal Beta, MDH Västerås.

Linus Källberg, vid akademin för innovation, design och teknik (IDT), försvarar sin doktorsavhandling i datavetenskap, den 10 januari, klockan 13.15 i sal Beta, MDH Västerås.

Titel: “Minimum Enclosing Balls and Ellipsoids in General Dimensions”.

Serienummer: 300.

Opponent är doktor Selin Damla Ahipasaoglu, Singapore University of Technology & Design, Singapore.

Betygsnämnden utgörs av professor Ulf Assarsson, Chalmers tekniska högskola, professor Anders Forsgren, Kungliga tekniska högskolan, och professor Peter Jonsson, Linköpings universitet.

Reserv är professor Hans Hansson, MDH.

Sammanfattning:

Avhandlingen studerar en typ av matematiska problem som går ut på att anpassa en enkel geometrisk figur så att den omsluter en given uppsättning datapunkter på ett så snävt sätt som möjligt. Att använda enkla omslutande figurer för att representera eller approximera stora datamängder och detaljerade geometriska strukturer har en lång rad tillämpningar inom t.ex. datorgrafik, statistik och maskininlärning. Effektiva metoder för att beräkna snävt åtsittande sådana figurer studeras därför flitigt inom bl.a. beräkningsgeometri och optimeringslära.

Två typer av omslutande figurer studeras i avhandlingen: bollar och ellipsoider. En boll kan även kallas för ett klot eller en sfär. En ellipsoid kan i sin tur beskrivas löst som en boll som har "klämts ihop" och/eller "dragits ut" i flera ledder. De specifika frågeställningar som behandlas rör alltså hur man effektivt hittar en boll eller en ellipsoid som har så liten volym som möjligt, samtidigt som ett givet "moln" av datapunkter ryms helt och hållet inuti figuren. P.g.a. sin mer flexibla form kan en ellipsoid approximera utseendet på den inneslutna punktmängden mer exakt än en boll kan. Å andra sidan är en minsta omslutande ellipsoid kostsammare att beräkna och använda än en minsta omslutande boll.

Problemen studeras i godtyckligt antal dimensioner. I endast en dimension är både en boll och en ellipsoid samma sak som ett intervall på tallinjen. I två dimensioner är en boll detsamma som en cirkel och en ellipsoid detsamma som en ellips. I fler än tre dimensioner beskrivs en boll enklast av att den ockuperar precis det utrymme som ligger inom ett visst avstånd - radien - ifrån bollens centrum. Denna beskrivning gäller oavsett hur många dimensioner bollens centrum och den omgivande rymden har. En högdimensionell ellipsoid beskrivs i sin tur enklast likt ovan, dvs. som en utdragen och/eller ihopklämd, högdimensionell boll.

Forskningsresultaten som läggs fram i avhandlingen innefattar nya metoder för att beräkna en minsta omslutande boll eller ellipsoid. Ett särskilt fokus ligger på att hantera stora datamängder, innehållandes många punkter, mer effektivt än befintliga metoder från forskningslitteraturen. Därtill kommer ett antal tekniker för att ytterligare snabba upp både de nya metoder som presenteras i avhandlingen och redan kända metoder. Några av dessa uppsnabbningstekniker bygger på nya teoretiska bidrag, andra drar nytta av moderna hårdvaruteknologier såsom flerkärniga processorer och grafikprocessorer.