In algoritmeihin geometria , quickhull on algoritmi varten laskettaessa kupera rungon . Se on jaa ja hallitse -algoritmi .
Huomaa ensin, että kupera kuori joukon E pisteitä on määritelty osajoukko F ja E . Algoritmin periaate on seuraava. Ensin löydetään vasemmanpuoleisin piste P ja oikeanpuoleisin piste Q (tasa-arvon ollessa kyseessä valitsemme mielivaltaisesti). Pisteet P ja Q kuuluvat kuperaan verhoon. Voimme sitten ratkaista ongelman etsimällä viivan (PQ) ja viivan alapuolella olevien pisteiden kuperan kirjekuoren , sitten liittämällä pisteluettelot (olematta toistamatta P: tä ja Q: ta ). Tällöin alakysymyksillä on rajoitetumpi muoto kuin alkuperäisellä esiintymällä: meillä on kaksi pistettä viivalla siten, että kaikki pisteet ovat viivan samalla puolella, sanotaan (PQ) vasemmalla puolella , ja kaikki pisteet, jotka kuuluvat linjalle ovat segmentissä [PQ] . Sitten löydetään piste H kauimpana viivasta. Yllä olevien pisteiden kupera verhokäyrä (PQ) saadaan sitten liittämällä pisteiden kupera kirjekuori (PH) vasemmalle ja pisteiden (HQ) vasemmalle puolelle . Voimme rekursiivisesti laskea nämä joukot (ne ovat samassa kokoonpanossa kuin aiemmin).
Algoritmi on samantyyppinen aikakompleksisuus että Lajittelualgoritmi pikalajittelu sanoen että pahimmassa tapauksessa ja keskiarvo .
Algoritmi esiintyy kirjassa Computational Geometry - An Introduction in 1985, jossa kirjoittajat pitävät ideoita useissa 1970-luvun artikkeleissa.