Analiza

Posmatrajmo neki trougao T koji zadovoljava uslove zadatka. Kako trougao T sadrži dati mnogougao M, a T je konveksan skup, važiće i K \subseteq T, gde je K konveksni omotač mnogougla M, jer je K po definiciji najmanji konveksan skup koji sadrži M. Dakle, u zadatku se traži da za dati mnogougao nađemo trougao najmanje površine koji sadrži njegov konveksni omotač, sa dodatnim ograničenjem da neka stranica trougla bude jednaka nekoj stranici datog mnogougla, neka je to stranica BC.

Temena B, C moraju biti susedna temena u konveksnom omotaču, jer se u suprotom stranica trougla nalazi u strogoj unutrašnjosti konveksnog omotača pa ga trougao ne može sadržati. Iz prethodno rečenog proizilazi da konveksni omotač i trougao imaju zajedničku stranicu. Posmatrajmo sada neku stranicu BC konveksnog omotača. Pretpostavićemo da naš trougao baš tu stranicu deli sa K. Kako nam treba trougao minimalne površine njegove preostale stranice moraju imati isti pravac kao i stranice koje su susedne stranici BC, neka su to stranice AB, CD. Stoga za svaku stranicu konveksnog omotača treba proveriti da li se produžeci susednih strana AB, CD seku sa odgovarajuće strane i da li je stranica BC konveksnog omotača ujedno i stranica mnogougla, što nam je dovoljno da zaključimo da postoji trougao sa odgovarajućim svojstvima. Zatim, nalazimo presek pravih E = AB \cap CD i to je treća tačka našeg trougla. Sada znamo sva temena trougla, odredimo površinu a zatim i razliku površina između njega i početnog mnogougla.

Smernice za algoritam

Zbog načina na koji su data temena mnogougla možemo u linearnom vremenu naći konveksni omotač. (videti članak na Vikipediji). Površina trougla kome znamo koordinate može se dobiti kao polovina intenziteta vektorskog proizvoda dve njegove stranice (odnosno odgovarajućih vektora). Označena površina nekonveksnog mnogougla može se naći kao zbir označenih površina proizvoljnog razbijanja tog mnogougla na trouglove - videti link. Dalje, potrebno je naći površinu trougla BCE gde je E presek pravih AB i CD. U teoriji, ovo se može uraditi nalaženjem jednačina te dve prave i rešavanjem sistema od dve jednačine sa dve nepoznate, a zatim primenom gore pomenute formule za površinu trougla. Međutim, problem nastaje zbog upotrebe tipa double za predstavljanje koeficijenata i rešenja ove jednačine. Srećom, postoji daleko jednostavniji način za nalaženje površine trougla BCE. Važi sledeća jednakost: P(BCE) = \frac{P(ABC) P(BCD)}{P(BCF)}, gde je F tačka dobijena pomeranjem tačke D za vektor CB, što se može relativno lako dokazati alatima elementarne geometrije.