Back

ⓘ Алгоритам увијања поклона




                                     

ⓘ Алгоритам увијања поклона

У случају равни алгоритам увијања поклона се назива још и Џарвисов марш, по Р. А. Џарвису који га је објавио 1973. године. Алгоритам увијања поклона је добио назив по начину на који се проналазе тачке конвексног омотача. Ако замислимо да су на местима тачака забодене усправне чиоде, алгоритам се може објаснити помоћу конца омотача који завежемо за почетну чиоду затегнемо га на напоље а затим обмотамо око скупа тачака, односно чиода, обухвативши тиме цео скуп унутар конца. Алгоритам увијања поклона је настао као оптимизација директног геометријског приступа за одређивање конвексног омотача. У случају тродимензионалног скупа тачака уместо конца бисмо користили папир за увијање, одакле долази и назив.

                                     

1. Алгоритам

Овај алгоритам се заснива на постепеном проширивању пута конвексног омотача. Основа алгоритма је изабирање екстремне тачке датог скупа, која засигурно припада конвексном омотачу. Узмимо за екстремну тачку ону са најмањом x-координатом, а уколико има више таквих ону са најмањом y-координатом. Означимо почетну тачку са p 1. Пролазећи кроз све тачке скупа, проналазимо ону која заједно са почетном тачком заклапа најмањи угао са x-осом. Нова тачка добија вредност p 2. Поступак се затим понавља за нову тачку омотача. Проналажење следеће тачке омотача захтева n-k корака, где је n укупан број тачака, а k број пронађених тачака омотача, што захтева временску сложеност од Оn.

                                     

2. Псеудокод

У наредном псеудокоду претпоставићемо да је изабрана почетна тачка она са највећом х координатом, односно најдеснија тачка скупа. Уколико има две или више тачака са највећом х коориднатом изабраћемо међу њима ону са најмањом у координатом.

                                     

3. Индуктивна хипотеза

Математичка основа за примену алгоритма за увијање поклона је геометријски метод за одређивање конвексног омотача скупа тачака. Оба метода се доказују индукцијом. АУП је директна последица примене следеће индуктивне хипотезе:

За дати скуп од n тачака у равни, умемо да пронађемо конвексни пут дужине k < n који је део конвексног омотача скупа.

                                     

4. Временска сложеност

За сваку тачку треба израчунати углове између правих ка свим преосталим теменима и x-осе и затим пронаћи минимални угао у скупу од n-k правих. Временска сложеност у општем случају је Оnh где је h број тачака конвексног омотача. У најгорем случају, све тачке скупа могу да припадају омотачу и па је стога временска сложеност алгоритма увијања поклона Оn 2.