\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\mathllap }[2][]{{#1#2}}\)
\(\newcommand {\mathrlap }[2][]{{#1#2}}\)
\(\newcommand {\mathclap }[2][]{{#1#2}}\)
\(\newcommand {\mathmbox }[1]{#1}\)
\(\newcommand {\clap }[1]{#1}\)
\(\newcommand {\LWRmathmakebox }[2][]{#2}\)
\(\newcommand {\mathmakebox }[1][]{\LWRmathmakebox }\)
\(\newcommand {\cramped }[2][]{{#1#2}}\)
\(\newcommand {\crampedllap }[2][]{{#1#2}}\)
\(\newcommand {\crampedrlap }[2][]{{#1#2}}\)
\(\newcommand {\crampedclap }[2][]{{#1#2}}\)
\(\newenvironment {crampedsubarray}[1]{}{}\)
\(\newcommand {\crampedsubstack }{}\)
\(\newcommand {\smashoperator }[2][]{#2\limits }\)
\(\newcommand {\adjustlimits }{}\)
\(\newcommand {\SwapAboveDisplaySkip }{}\)
\(\require {extpfeil}\)
\(\Newextarrow \xleftrightarrow {10,10}{0x2194}\)
\(\Newextarrow \xLeftarrow {10,10}{0x21d0}\)
\(\Newextarrow \xhookleftarrow {10,10}{0x21a9}\)
\(\Newextarrow \xmapsto {10,10}{0x21a6}\)
\(\Newextarrow \xRightarrow {10,10}{0x21d2}\)
\(\Newextarrow \xLeftrightarrow {10,10}{0x21d4}\)
\(\Newextarrow \xhookrightarrow {10,10}{0x21aa}\)
\(\Newextarrow \xrightharpoondown {10,10}{0x21c1}\)
\(\Newextarrow \xleftharpoondown {10,10}{0x21bd}\)
\(\Newextarrow \xrightleftharpoons {10,10}{0x21cc}\)
\(\Newextarrow \xrightharpoonup {10,10}{0x21c0}\)
\(\Newextarrow \xleftharpoonup {10,10}{0x21bc}\)
\(\Newextarrow \xleftrightharpoons {10,10}{0x21cb}\)
\(\newcommand {\LWRdounderbracket }[3]{\underset {#3}{\underline {#1}}}\)
\(\newcommand {\LWRunderbracket }[2][]{\LWRdounderbracket {#2}}\)
\(\newcommand {\underbracket }[1][]{\LWRunderbracket }\)
\(\newcommand {\LWRdooverbracket }[3]{\overset {#3}{\overline {#1}}}\)
\(\newcommand {\LWRoverbracket }[2][]{\LWRdooverbracket {#2}}\)
\(\newcommand {\overbracket }[1][]{\LWRoverbracket }\)
\(\newcommand {\LATEXunderbrace }[1]{\underbrace {#1}}\)
\(\newcommand {\LATEXoverbrace }[1]{\overbrace {#1}}\)
\(\newenvironment {matrix*}[1][]{\begin {matrix}}{\end {matrix}}\)
\(\newenvironment {pmatrix*}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bmatrix*}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bmatrix*}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vmatrix*}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vmatrix*}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newenvironment {smallmatrix*}[1][]{\begin {matrix}}{\end {matrix}}\)
\(\newenvironment {psmallmatrix*}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bsmallmatrix*}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bsmallmatrix*}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vsmallmatrix*}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vsmallmatrix*}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newenvironment {psmallmatrix}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bsmallmatrix}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bsmallmatrix}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vsmallmatrix}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vsmallmatrix}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newcommand {\LWRmultlined }[1][]{\begin {multline*}}\)
\(\newenvironment {multlined}[1][]{\LWRmultlined }{\end {multline*}}\)
\(\let \LWRorigshoveleft \shoveleft \)
\(\renewcommand {\shoveleft }[1][]{\LWRorigshoveleft }\)
\(\let \LWRorigshoveright \shoveright \)
\(\renewcommand {\shoveright }[1][]{\LWRorigshoveright }\)
\(\newenvironment {dcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {dcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {rcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {rcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {drcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {drcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {cases*}{\begin {cases}}{\end {cases}}\)
\(\newcommand {\MoveEqLeft }[1][]{}\)
\(\def \LWRAboxed #1!|!{\fbox {\(#1\)}&\fbox {\(#2\)}} \newcommand {\Aboxed }[1]{\LWRAboxed #1&&!|!} \)
\( \newcommand {\LWRABLines }[1][\Updownarrow ]{#1 \notag \\}\newcommand {\ArrowBetweenLines }{\ifstar \LWRABLines \LWRABLines } \)
\(\newcommand {\shortintertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\vdotswithin }[1]{\hspace {.5em}\vdots }\)
\(\newcommand {\LWRshortvdotswithinstar }[1]{\vdots \hspace {.5em} & \\}\)
\(\newcommand {\LWRshortvdotswithinnostar }[1]{& \hspace {.5em}\vdots \\}\)
\(\newcommand {\shortvdotswithin }{\ifstar \LWRshortvdotswithinstar \LWRshortvdotswithinnostar }\)
\(\newcommand {\MTFlushSpaceAbove }{}\)
\(\newcommand {\MTFlushSpaceBelow }{\\}\)
\(\newcommand \lparen {(}\)
\(\newcommand \rparen {)}\)
\(\newcommand {\ordinarycolon }{:}\)
\(\newcommand {\vcentcolon }{\mathrel {\mathop \ordinarycolon }}\)
\(\newcommand \dblcolon {\vcentcolon \vcentcolon }\)
\(\newcommand \coloneqq {\vcentcolon =}\)
\(\newcommand \Coloneqq {\dblcolon =}\)
\(\newcommand \coloneq {\vcentcolon {-}}\)
\(\newcommand \Coloneq {\dblcolon {-}}\)
\(\newcommand \eqqcolon {=\vcentcolon }\)
\(\newcommand \Eqqcolon {=\dblcolon }\)
\(\newcommand \eqcolon {\mathrel {-}\vcentcolon }\)
\(\newcommand \Eqcolon {\mathrel {-}\dblcolon }\)
\(\newcommand \colonapprox {\vcentcolon \approx }\)
\(\newcommand \Colonapprox {\dblcolon \approx }\)
\(\newcommand \colonsim {\vcentcolon \sim }\)
\(\newcommand \Colonsim {\dblcolon \sim }\)
\(\newcommand {\nuparrow }{\mathrel {\cancel {\uparrow }}}\)
\(\newcommand {\ndownarrow }{\mathrel {\cancel {\downarrow }}}\)
\(\newcommand {\bigtimes }{\mathop {\Large \times }\limits }\)
\(\newcommand {\prescript }[3]{{}^{#1}_{#2}#3}\)
\(\newenvironment {lgathered}{\begin {gathered}}{\end {gathered}}\)
\(\newenvironment {rgathered}{\begin {gathered}}{\end {gathered}}\)
\(\newcommand {\splitfrac }[2]{{}^{#1}_{#2}}\)
\(\let \splitdfrac \splitfrac \)
\(\newcommand {\LWRoverlaysymbols }[2]{\mathord {\smash {\mathop {#2\strut }\limits ^{\smash {\lower 3ex{#1}}}}\strut }}\)
\(\newcommand{\alphaup}{\unicode{x03B1}}\)
\(\newcommand{\betaup}{\unicode{x03B2}}\)
\(\newcommand{\gammaup}{\unicode{x03B3}}\)
\(\newcommand{\digammaup}{\unicode{x03DD}}\)
\(\newcommand{\deltaup}{\unicode{x03B4}}\)
\(\newcommand{\epsilonup}{\unicode{x03F5}}\)
\(\newcommand{\varepsilonup}{\unicode{x03B5}}\)
\(\newcommand{\zetaup}{\unicode{x03B6}}\)
\(\newcommand{\etaup}{\unicode{x03B7}}\)
\(\newcommand{\thetaup}{\unicode{x03B8}}\)
\(\newcommand{\varthetaup}{\unicode{x03D1}}\)
\(\newcommand{\iotaup}{\unicode{x03B9}}\)
\(\newcommand{\kappaup}{\unicode{x03BA}}\)
\(\newcommand{\varkappaup}{\unicode{x03F0}}\)
\(\newcommand{\lambdaup}{\unicode{x03BB}}\)
\(\newcommand{\muup}{\unicode{x03BC}}\)
\(\newcommand{\nuup}{\unicode{x03BD}}\)
\(\newcommand{\xiup}{\unicode{x03BE}}\)
\(\newcommand{\omicronup}{\unicode{x03BF}}\)
\(\newcommand{\piup}{\unicode{x03C0}}\)
\(\newcommand{\varpiup}{\unicode{x03D6}}\)
\(\newcommand{\rhoup}{\unicode{x03C1}}\)
\(\newcommand{\varrhoup}{\unicode{x03F1}}\)
\(\newcommand{\sigmaup}{\unicode{x03C3}}\)
\(\newcommand{\varsigmaup}{\unicode{x03C2}}\)
\(\newcommand{\tauup}{\unicode{x03C4}}\)
\(\newcommand{\upsilonup}{\unicode{x03C5}}\)
\(\newcommand{\phiup}{\unicode{x03D5}}\)
\(\newcommand{\varphiup}{\unicode{x03C6}}\)
\(\newcommand{\chiup}{\unicode{x03C7}}\)
\(\newcommand{\psiup}{\unicode{x03C8}}\)
\(\newcommand{\omegaup}{\unicode{x03C9}}\)
\(\newcommand{\Alphaup}{\unicode{x0391}}\)
\(\newcommand{\Betaup}{\unicode{x0392}}\)
\(\newcommand{\Gammaup}{\unicode{x0393}}\)
\(\newcommand{\Digammaup}{\unicode{x03DC}}\)
\(\newcommand{\Deltaup}{\unicode{x0394}}\)
\(\newcommand{\Epsilonup}{\unicode{x0395}}\)
\(\newcommand{\Zetaup}{\unicode{x0396}}\)
\(\newcommand{\Etaup}{\unicode{x0397}}\)
\(\newcommand{\Thetaup}{\unicode{x0398}}\)
\(\newcommand{\Varthetaup}{\unicode{x03F4}}\)
\(\newcommand{\Iotaup}{\unicode{x0399}}\)
\(\newcommand{\Kappaup}{\unicode{x039A}}\)
\(\newcommand{\Lambdaup}{\unicode{x039B}}\)
\(\newcommand{\Muup}{\unicode{x039C}}\)
\(\newcommand{\Nuup}{\unicode{x039D}}\)
\(\newcommand{\Xiup}{\unicode{x039E}}\)
\(\newcommand{\Omicronup}{\unicode{x039F}}\)
\(\newcommand{\Piup}{\unicode{x03A0}}\)
\(\newcommand{\Varpiup}{\unicode{x03D6}}\)
\(\newcommand{\Rhoup}{\unicode{x03A1}}\)
\(\newcommand{\Sigmaup}{\unicode{x03A3}}\)
\(\newcommand{\Tauup}{\unicode{x03A4}}\)
\(\newcommand{\Upsilonup}{\unicode{x03A5}}\)
\(\newcommand{\Phiup}{\unicode{x03A6}}\)
\(\newcommand{\Chiup}{\unicode{x03A7}}\)
\(\newcommand{\Psiup}{\unicode{x03A8}}\)
\(\newcommand{\Omegaup}{\unicode{x03A9}}\)
\(\newcommand{\alphait}{\unicode{x1D6FC}}\)
\(\newcommand{\betait}{\unicode{x1D6FD}}\)
\(\newcommand{\gammait}{\unicode{x1D6FE}}\)
\(\newcommand{\digammait}{\mathit{\unicode{x03DD}}}\)
\(\newcommand{\deltait}{\unicode{x1D6FF}}\)
\(\newcommand{\epsilonit}{\unicode{x1D716}}\)
\(\newcommand{\varepsilonit}{\unicode{x1D700}}\)
\(\newcommand{\zetait}{\unicode{x1D701}}\)
\(\newcommand{\etait}{\unicode{x1D702}}\)
\(\newcommand{\thetait}{\unicode{x1D703}}\)
\(\newcommand{\varthetait}{\unicode{x1D717}}\)
\(\newcommand{\iotait}{\unicode{x1D704}}\)
\(\newcommand{\kappait}{\unicode{x1D705}}\)
\(\newcommand{\varkappait}{\unicode{x1D718}}\)
\(\newcommand{\lambdait}{\unicode{x1D706}}\)
\(\newcommand{\muit}{\unicode{x1D707}}\)
\(\newcommand{\nuit}{\unicode{x1D708}}\)
\(\newcommand{\xiit}{\unicode{x1D709}}\)
\(\newcommand{\omicronit}{\unicode{x1D70A}}\)
\(\newcommand{\piit}{\unicode{x1D70B}}\)
\(\newcommand{\varpiit}{\unicode{x1D71B}}\)
\(\newcommand{\rhoit}{\unicode{x1D70C}}\)
\(\newcommand{\varrhoit}{\unicode{x1D71A}}\)
\(\newcommand{\sigmait}{\unicode{x1D70E}}\)
\(\newcommand{\varsigmait}{\unicode{x1D70D}}\)
\(\newcommand{\tauit}{\unicode{x1D70F}}\)
\(\newcommand{\upsilonit}{\unicode{x1D710}}\)
\(\newcommand{\phiit}{\unicode{x1D719}}\)
\(\newcommand{\varphiit}{\unicode{x1D711}}\)
\(\newcommand{\chiit}{\unicode{x1D712}}\)
\(\newcommand{\psiit}{\unicode{x1D713}}\)
\(\newcommand{\omegait}{\unicode{x1D714}}\)
\(\newcommand{\Alphait}{\unicode{x1D6E2}}\)
\(\newcommand{\Betait}{\unicode{x1D6E3}}\)
\(\newcommand{\Gammait}{\unicode{x1D6E4}}\)
\(\newcommand{\Digammait}{\mathit{\unicode{x03DC}}}\)
\(\newcommand{\Deltait}{\unicode{x1D6E5}}\)
\(\newcommand{\Epsilonit}{\unicode{x1D6E6}}\)
\(\newcommand{\Zetait}{\unicode{x1D6E7}}\)
\(\newcommand{\Etait}{\unicode{x1D6E8}}\)
\(\newcommand{\Thetait}{\unicode{x1D6E9}}\)
\(\newcommand{\Varthetait}{\unicode{x1D6F3}}\)
\(\newcommand{\Iotait}{\unicode{x1D6EA}}\)
\(\newcommand{\Kappait}{\unicode{x1D6EB}}\)
\(\newcommand{\Lambdait}{\unicode{x1D6EC}}\)
\(\newcommand{\Muit}{\unicode{x1D6ED}}\)
\(\newcommand{\Nuit}{\unicode{x1D6EE}}\)
\(\newcommand{\Xiit}{\unicode{x1D6EF}}\)
\(\newcommand{\Omicronit}{\unicode{x1D6F0}}\)
\(\newcommand{\Piit}{\unicode{x1D6F1}}\)
\(\newcommand{\Rhoit}{\unicode{x1D6F2}}\)
\(\newcommand{\Sigmait}{\unicode{x1D6F4}}\)
\(\newcommand{\Tauit}{\unicode{x1D6F5}}\)
\(\newcommand{\Upsilonit}{\unicode{x1D6F6}}\)
\(\newcommand{\Phiit}{\unicode{x1D6F7}}\)
\(\newcommand{\Chiit}{\unicode{x1D6F8}}\)
\(\newcommand{\Psiit}{\unicode{x1D6F9}}\)
\(\newcommand{\Omegait}{\unicode{x1D6FA}}\)
\(\let \digammaup \Digammaup \)
\(\renewcommand {\digammait }{\mathit {\digammaup }}\)
\(\newcommand {\smallin }{\unicode {x220A}}\)
\(\newcommand {\smallowns }{\unicode {x220D}}\)
\(\newcommand {\notsmallin }{\LWRoverlaysymbols {/}{\unicode {x220A}}}\)
\(\newcommand {\notsmallowns }{\LWRoverlaysymbols {/}{\unicode {x220D}}}\)
\(\newcommand {\rightangle }{\unicode {x221F}}\)
\(\newcommand {\intclockwise }{\unicode {x2231}}\)
\(\newcommand {\ointclockwise }{\unicode {x2232}}\)
\(\newcommand {\ointctrclockwise }{\unicode {x2233}}\)
\(\newcommand {\oiint }{\unicode {x222F}}\)
\(\newcommand {\oiiint }{\unicode {x2230}}\)
\(\newcommand {\ddag }{\unicode {x2021}}\)
\(\newcommand {\P }{\unicode {x00B6}}\)
\(\newcommand {\copyright }{\unicode {x00A9}}\)
\(\newcommand {\dag }{\unicode {x2020}}\)
\(\newcommand {\pounds }{\unicode {x00A3}}\)
\(\newcommand {\iddots }{\unicode {x22F0}}\)
\(\newcommand {\utimes }{\overline {\times }}\)
\(\newcommand {\dtimes }{\underline {\times }}\)
\(\newcommand {\udtimes }{\overline {\underline {\times }}}\)
\(\newcommand {\leftwave }{\left \{}\)
\(\newcommand {\rightwave }{\right \}}\)
\(\newcommand {\toprule }[1][]{\hline }\)
\(\let \midrule \toprule \)
\(\let \bottomrule \toprule \)
\(\newcommand {\cmidrule }[2][]{}\)
\(\newcommand {\morecmidrules }{}\)
\(\newcommand {\specialrule }[3]{\hline }\)
\(\newcommand {\addlinespace }[1][]{}\)
\(\newcommand {\LWRsubmultirow }[2][]{#2}\)
\(\newcommand {\LWRmultirow }[2][]{\LWRsubmultirow }\)
\(\newcommand {\multirow }[2][]{\LWRmultirow }\)
\(\newcommand {\mrowcell }{}\)
\(\newcommand {\mcolrowcell }{}\)
\(\newcommand {\STneed }[1]{}\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\newcommand {\tothe }[1]{^{#1}}\)
\(\newcommand {\raiseto }[2]{{#2}^{#1}}\)
\(\newcommand {\ang }[2][]{(\mathrm {#2})\degree }\)
\(\newcommand {\num }[2][]{\mathrm {#2}}\)
\(\newcommand {\si }[2][]{\mathrm {#2}}\)
\(\newcommand {\LWRSI }[2][]{\mathrm {#1\LWRSInumber \,#2}}\)
\(\newcommand {\SI }[2][]{\def \LWRSInumber {#2}\LWRSI }\)
\(\newcommand {\numlist }[2][]{\mathrm {#2}}\)
\(\newcommand {\numrange }[3][]{\mathrm {#2\,\unicode {x2013}\,#3}}\)
\(\newcommand {\SIlist }[3][]{\mathrm {#2\,#3}}\)
\(\newcommand {\SIrange }[4][]{\mathrm {#2\,#4\,\unicode {x2013}\,#3\,#4}}\)
\(\newcommand {\tablenum }[2][]{\mathrm {#2}}\)
\(\newcommand {\ampere }{\mathrm {A}}\)
\(\newcommand {\candela }{\mathrm {cd}}\)
\(\newcommand {\kelvin }{\mathrm {K}}\)
\(\newcommand {\kilogram }{\mathrm {kg}}\)
\(\newcommand {\metre }{\mathrm {m}}\)
\(\newcommand {\mole }{\mathrm {mol}}\)
\(\newcommand {\second }{\mathrm {s}}\)
\(\newcommand {\becquerel }{\mathrm {Bq}}\)
\(\newcommand {\degreeCelsius }{\unicode {x2103}}\)
\(\newcommand {\coulomb }{\mathrm {C}}\)
\(\newcommand {\farad }{\mathrm {F}}\)
\(\newcommand {\gray }{\mathrm {Gy}}\)
\(\newcommand {\hertz }{\mathrm {Hz}}\)
\(\newcommand {\henry }{\mathrm {H}}\)
\(\newcommand {\joule }{\mathrm {J}}\)
\(\newcommand {\katal }{\mathrm {kat}}\)
\(\newcommand {\lumen }{\mathrm {lm}}\)
\(\newcommand {\lux }{\mathrm {lx}}\)
\(\newcommand {\newton }{\mathrm {N}}\)
\(\newcommand {\ohm }{\mathrm {\Omega }}\)
\(\newcommand {\pascal }{\mathrm {Pa}}\)
\(\newcommand {\radian }{\mathrm {rad}}\)
\(\newcommand {\siemens }{\mathrm {S}}\)
\(\newcommand {\sievert }{\mathrm {Sv}}\)
\(\newcommand {\steradian }{\mathrm {sr}}\)
\(\newcommand {\tesla }{\mathrm {T}}\)
\(\newcommand {\volt }{\mathrm {V}}\)
\(\newcommand {\watt }{\mathrm {W}}\)
\(\newcommand {\weber }{\mathrm {Wb}}\)
\(\newcommand {\day }{\mathrm {d}}\)
\(\newcommand {\degree }{\mathrm {^\circ }}\)
\(\newcommand {\hectare }{\mathrm {ha}}\)
\(\newcommand {\hour }{\mathrm {h}}\)
\(\newcommand {\litre }{\mathrm {l}}\)
\(\newcommand {\liter }{\mathrm {L}}\)
\(\newcommand {\arcminute }{^\prime }\)
\(\newcommand {\minute }{\mathrm {min}}\)
\(\newcommand {\arcsecond }{^{\prime \prime }}\)
\(\newcommand {\tonne }{\mathrm {t}}\)
\(\newcommand {\astronomicalunit }{au}\)
\(\newcommand {\atomicmassunit }{u}\)
\(\newcommand {\bohr }{\mathit {a}_0}\)
\(\newcommand {\clight }{\mathit {c}_0}\)
\(\newcommand {\dalton }{\mathrm {D}_\mathrm {a}}\)
\(\newcommand {\electronmass }{\mathit {m}_{\mathrm {e}}}\)
\(\newcommand {\electronvolt }{\mathrm {eV}}\)
\(\newcommand {\elementarycharge }{\mathit {e}}\)
\(\newcommand {\hartree }{\mathit {E}_{\mathrm {h}}}\)
\(\newcommand {\planckbar }{\mathit {\unicode {x210F}}}\)
\(\newcommand {\angstrom }{\mathrm {\unicode {x212B}}}\)
\(\let \LWRorigbar \bar \)
\(\newcommand {\bar }{\mathrm {bar}}\)
\(\newcommand {\barn }{\mathrm {b}}\)
\(\newcommand {\bel }{\mathrm {B}}\)
\(\newcommand {\decibel }{\mathrm {dB}}\)
\(\newcommand {\knot }{\mathrm {kn}}\)
\(\newcommand {\mmHg }{\mathrm {mmHg}}\)
\(\newcommand {\nauticalmile }{\mathrm {M}}\)
\(\newcommand {\neper }{\mathrm {Np}}\)
\(\newcommand {\yocto }{\mathrm {y}}\)
\(\newcommand {\zepto }{\mathrm {z}}\)
\(\newcommand {\atto }{\mathrm {a}}\)
\(\newcommand {\femto }{\mathrm {f}}\)
\(\newcommand {\pico }{\mathrm {p}}\)
\(\newcommand {\nano }{\mathrm {n}}\)
\(\newcommand {\micro }{\mathrm {\unicode {x00B5}}}\)
\(\newcommand {\milli }{\mathrm {m}}\)
\(\newcommand {\centi }{\mathrm {c}}\)
\(\newcommand {\deci }{\mathrm {d}}\)
\(\newcommand {\deca }{\mathrm {da}}\)
\(\newcommand {\hecto }{\mathrm {h}}\)
\(\newcommand {\kilo }{\mathrm {k}}\)
\(\newcommand {\mega }{\mathrm {M}}\)
\(\newcommand {\giga }{\mathrm {G}}\)
\(\newcommand {\tera }{\mathrm {T}}\)
\(\newcommand {\peta }{\mathrm {P}}\)
\(\newcommand {\exa }{\mathrm {E}}\)
\(\newcommand {\zetta }{\mathrm {Z}}\)
\(\newcommand {\yotta }{\mathrm {Y}}\)
\(\newcommand {\percent }{\mathrm {\%}}\)
\(\newcommand {\meter }{\mathrm {m}}\)
\(\newcommand {\metre }{\mathrm {m}}\)
\(\newcommand {\gram }{\mathrm {g}}\)
\(\newcommand {\kg }{\kilo \gram }\)
\(\newcommand {\of }[1]{_{\mathrm {#1}}}\)
\(\newcommand {\squared }{^2}\)
\(\newcommand {\square }[1]{\mathrm {#1}^2}\)
\(\newcommand {\cubed }{^3}\)
\(\newcommand {\cubic }[1]{\mathrm {#1}^3}\)
\(\newcommand {\per }{/}\)
\(\newcommand {\celsius }{\unicode {x2103}}\)
\(\newcommand {\fg }{\femto \gram }\)
\(\newcommand {\pg }{\pico \gram }\)
\(\newcommand {\ng }{\nano \gram }\)
\(\newcommand {\ug }{\micro \gram }\)
\(\newcommand {\mg }{\milli \gram }\)
\(\newcommand {\g }{\gram }\)
\(\newcommand {\kg }{\kilo \gram }\)
\(\newcommand {\amu }{\mathrm {u}}\)
\(\newcommand {\nm }{\nano \metre }\)
\(\newcommand {\um }{\micro \metre }\)
\(\newcommand {\mm }{\milli \metre }\)
\(\newcommand {\cm }{\centi \metre }\)
\(\newcommand {\dm }{\deci \metre }\)
\(\newcommand {\m }{\metre }\)
\(\newcommand {\km }{\kilo \metre }\)
\(\newcommand {\as }{\atto \second }\)
\(\newcommand {\fs }{\femto \second }\)
\(\newcommand {\ps }{\pico \second }\)
\(\newcommand {\ns }{\nano \second }\)
\(\newcommand {\us }{\micro \second }\)
\(\newcommand {\ms }{\milli \second }\)
\(\newcommand {\s }{\second }\)
\(\newcommand {\fmol }{\femto \mol }\)
\(\newcommand {\pmol }{\pico \mol }\)
\(\newcommand {\nmol }{\nano \mol }\)
\(\newcommand {\umol }{\micro \mol }\)
\(\newcommand {\mmol }{\milli \mol }\)
\(\newcommand {\mol }{\mol }\)
\(\newcommand {\kmol }{\kilo \mol }\)
\(\newcommand {\pA }{\pico \ampere }\)
\(\newcommand {\nA }{\nano \ampere }\)
\(\newcommand {\uA }{\micro \ampere }\)
\(\newcommand {\mA }{\milli \ampere }\)
\(\newcommand {\A }{\ampere }\)
\(\newcommand {\kA }{\kilo \ampere }\)
\(\newcommand {\ul }{\micro \litre }\)
\(\newcommand {\ml }{\milli \litre }\)
\(\newcommand {\l }{\litre }\)
\(\newcommand {\hl }{\hecto \litre }\)
\(\newcommand {\uL }{\micro \liter }\)
\(\newcommand {\mL }{\milli \liter }\)
\(\newcommand {\L }{\liter }\)
\(\newcommand {\hL }{\hecto \liter }\)
\(\newcommand {\mHz }{\milli \hertz }\)
\(\newcommand {\Hz }{\hertz }\)
\(\newcommand {\kHz }{\kilo \hertz }\)
\(\newcommand {\MHz }{\mega \hertz }\)
\(\newcommand {\GHz }{\giga \hertz }\)
\(\newcommand {\THz }{\tera \hertz }\)
\(\newcommand {\mN }{\milli \newton }\)
\(\newcommand {\N }{\newton }\)
\(\newcommand {\kN }{\kilo \newton }\)
\(\newcommand {\MN }{\mega \newton }\)
\(\newcommand {\Pa }{\pascal }\)
\(\newcommand {\kPa }{\kilo \pascal }\)
\(\newcommand {\MPa }{\mega \pascal }\)
\(\newcommand {\GPa }{\giga \pascal }\)
\(\newcommand {\mohm }{\milli \ohm }\)
\(\newcommand {\kohm }{\kilo \ohm }\)
\(\newcommand {\Mohm }{\mega \ohm }\)
\(\newcommand {\pV }{\pico \volt }\)
\(\newcommand {\nV }{\nano \volt }\)
\(\newcommand {\uV }{\micro \volt }\)
\(\newcommand {\mV }{\milli \volt }\)
\(\newcommand {\V }{\volt }\)
\(\newcommand {\kV }{\kilo \volt }\)
\(\newcommand {\W }{\watt }\)
\(\newcommand {\uW }{\micro \watt }\)
\(\newcommand {\mW }{\milli \watt }\)
\(\newcommand {\kW }{\kilo \watt }\)
\(\newcommand {\MW }{\mega \watt }\)
\(\newcommand {\GW }{\giga \watt }\)
\(\newcommand {\J }{\joule }\)
\(\newcommand {\uJ }{\micro \joule }\)
\(\newcommand {\mJ }{\milli \joule }\)
\(\newcommand {\kJ }{\kilo \joule }\)
\(\newcommand {\eV }{\electronvolt }\)
\(\newcommand {\meV }{\milli \electronvolt }\)
\(\newcommand {\keV }{\kilo \electronvolt }\)
\(\newcommand {\MeV }{\mega \electronvolt }\)
\(\newcommand {\GeV }{\giga \electronvolt }\)
\(\newcommand {\TeV }{\tera \electronvolt }\)
\(\newcommand {\kWh }{\kilo \watt \hour }\)
\(\newcommand {\F }{\farad }\)
\(\newcommand {\fF }{\femto \farad }\)
\(\newcommand {\pF }{\pico \farad }\)
\(\newcommand {\K }{\mathrm {K}}\)
\(\newcommand {\dB }{\mathrm {dB}}\)
\(\newcommand {\kibi }{\mathrm {Ki}}\)
\(\newcommand {\mebi }{\mathrm {Mi}}\)
\(\newcommand {\gibi }{\mathrm {Gi}}\)
\(\newcommand {\tebi }{\mathrm {Ti}}\)
\(\newcommand {\pebi }{\mathrm {Pi}}\)
\(\newcommand {\exbi }{\mathrm {Ei}}\)
\(\newcommand {\zebi }{\mathrm {Zi}}\)
\(\newcommand {\yobi }{\mathrm {Yi}}\)
\(\require {mhchem}\)
\(\require {cancel}\)
\(\newcommand {\fint }{âĺŊ}\)
\(\newcommand {\hdots }{\cdots }\)
\(\newcommand {\mathnormal }[1]{#1}\)
\(\newcommand {\vecs }[2]{\vec {#1}_{#2}}\)
\(\renewcommand {\A }{\mathcal {A}}\)
\(\newcommand {\D }{\mathcal {D}}\)
\(\renewcommand {\H }{\mathcal {H}}\)
\(\renewcommand {\L }{\mathcal {L}}\)
\(\renewcommand {\O }{\mathcal {O}}\)
\(\renewcommand {\P }{\mathcal {P}}\)
\(\newcommand {\T }{\mathcal {T}}\)
\(\newcommand {\EE }{\mathbb {E}}\)
\(\newcommand {\PP }{\mathbb {P}}\)
\(\newcommand {\DT }{\operatorname {DT}}\)
\(\newcommand {\dcup }{\mathbin {\dot {\cup }}}\)
\(\newcommand {\parent }{\operatorname {parent}}\)
\(\newcommand {\cc }{\operatorname {cc}}\)
\(\newcommand {\interior }{\operatorname {int}}\)
\(\newcommand {\CH }{\operatorname {CH}}\)
\(\newcommand {\sgn }{\operatorname {sgn}}\)
\(\newcommand {\zone }{\operatorname {zone}}\)
\(\newcommand {\code }[1]{\texttt {#1}}\)
\(\newcommand {\name }[1]{\textsc {#1}}\)
\(\newcommand {\smallpmatrix }[1]{\left (\begin {smallmatrix}#1\end {smallmatrix}\right )}\)
\(\newcommand {\matlab }{{\fontfamily {bch}\scshape \selectfont {}Matlab}}\)
\(\newcommand {\innerproduct }[1]{\left \langle {#1}\right \rangle }\)
\(\newcommand {\norm }[1]{\left \Vert {#1}\right \Vert }\)
\(\renewcommand {\natural }{\mathbb {N}}\)
\(\newcommand {\integer }{\mathbb {Z}}\)
\(\newcommand {\rational }{\mathbb {Q}}\)
\(\newcommand {\real }{\mathbb {R}}\)
\(\newcommand {\complex }{\mathbb {C}}\)
\(\renewcommand {\d }{\mathop {}\!\mathrm {d}}\)
\(\newcommand {\dr }{\d {}r}\)
\(\newcommand {\ds }{\d {}s}\)
\(\newcommand {\dt }{\d {}t}\)
\(\newcommand {\du }{\d {}u}\)
\(\newcommand {\dv }{\d {}v}\)
\(\newcommand {\dw }{\d {}w}\)
\(\newcommand {\dx }{\d {}x}\)
\(\newcommand {\dy }{\d {}y}\)
\(\newcommand {\dz }{\d {}z}\)
\(\newcommand {\dsigma }{\d {}\sigma }\)
\(\newcommand {\dphi }{\d {}\phi }\)
\(\newcommand {\dvarphi }{\d {}\varphi }\)
\(\newcommand {\dtau }{\d {}\tau }\)
\(\newcommand {\dxi }{\d {}\xi }\)
\(\newcommand {\dtheta }{\d {}\theta }\)
\(\newcommand {\tp }{\mathrm {T}}\)
konvexe Hülle: Sei \(P \subset \real ^d\) eine endliche Punktmenge mit \(n := |P|\).
Die konvexe Hülle \(\CH (P)\) ist die minimale konvexe Menge \(C \subset \real ^d\) mit \(P \subset C\).
Wenn man \(\CH (P)\) berechnet, interessiert meist eine Beschreibung des Rands von \(\CH (P)\). In \(\real ^2\) ist diese mit der Abfolge der Punkte auf dem Rand von \(\CH (P)\) gegen den Uhrzeigersinn gegeben. In \(\real
^3\) reicht der Oberflächengraph des entsprechenden Polytops, der als planarer Graph zur Speicherung \(\O (n)\) Platz benötigt. In \(d\) Dimensionen braucht man \(\O (n^{\lfloor d/2 \rfloor })\) Platz.
Zur Berechnung von \(\CH (P)\) benötigt man i. A. \(\Omega (n \log n)\) Zeit (wenn alle Punkte auf dem Rand liegen), denn Sortieren ist auf das Konvexe-Hülle-Problem reduzierbar: Gegebene
Zahlen \(x_1, \dotsc , x_n \in \real \) lassen sich durch Berechnung von \(\CH (\{(x_1, x_1^2), \dotsc , (x_n, x_n^2)\})\) sortieren, weil die Standardparabel selbst konvex ist und der CH-Algorithmus die Punkte auf
dem Rand in der richtigen Reihenfolge ausgibt. Weil aber vergleichsbasiertes Sortieren (deterministisch oder randomisiert) \(\Omega (n \log n)\) Zeit benötigt, benötigt auch jeder CH-Algorithmus \(\Omega (n
\log n)\) Zeit.
Genauer lässt sich zeigen: Ist \(h\) die Anzahl der Punkte aus \(P\) auf dem Rand von \(\CH (P)\), dann ist die untere Laufzeit-Schranke \(\Omega (n \log h)\).
Graham-Scan-Algorithmus
Graham-Scan-Algorithmus:
Der Graham-Scan-Algorithmus findet die konvexe Hülle in \(\real ^2\) wie folgt.
Finde den Punkt \(p_0 \in P\) mit minimaler \(y\)-Koordinate.
Sortiere die Punkte \(p \in P \setminus \{p_0\}\) aufsteigend gemäß dem Winkel von \(\overline {p_0 p}\) zur nach rechts zeigenden Horizontalen und erhalte \(p_1, \dotsc , p_{n-1}\).
Konstruiere das Polygon \(p_0 p_1 \dotsb p_{n-1} p_0\).
Gehe auf dem Rand des Polygons entlang und entferne Konkavitäten:
Starte bei \(i = 0\).
Prüfe, ob das Teilstück \(p_i p_{i+1} p_{i+2}\) einen Links- oder Rechtsknick macht (\(p_{i+1}\) und \(p_{i+2}\) am Ende entsprechend definiert).
Bei einem Rechtsknick entferne den Punkt \(p_{i+1}\) aus dem Polygon und nummeriere die nachfolgenden Punkte neu durch (d. h. \(p_{i+2} \rightarrow p_{i+1}\) usw.). Anschließend ziehe von \(i\)
eins ab. (Dadurch werden keine Schnittpunkte erzeugt.)
Beende, wenn \(p_0\) wieder der aktuelle Punkt ist.
Der Graham-Scan-Algorithmus kann ohne Weiteres nicht auf höhere Dimensionen verallgemeinert werden. In der Praxis werden die Winkel bei Schritt (2) nicht ausgerechnet, sondern mit einem Links-Rechts-Test
wird ermittelt, ob \(p_j\) links oder rechts von \(\overline {p_0 p_i}\) liegt (bei der Vergleichsroutine im Sortieralgorithmus).
Zeitaufwand: \(\O (n \log n)\)
Beweis: Schritt (1) benötigt Zeit \(\O (n)\). Schritt (2) sortiert \(n\) Punkte und benötigt daher Zeit \(\O (n \log n)\). Bei Schritt (4) wird einmal durch das Polygon
mit \(n\) Ecken gegangen. Es werden zwar „Rückschritte“ gemacht, allerdings wird bei jedem Rückschritt eine Ecke entfernt, was auch höchstens \(n\) Mal passieren kann. Daher benötigt
Schritt (4) Zeit \(\O (n)\) und der gesamte Algorithmus hat den Zeitaufwand \(\O (n \log n)\).
Gift-Wrapping-Algorithmus
Gift-Wrapping-Algorithmus:
Der Gift-Wrapping-Algorithmus findet die konvexe Hülle in \(\real ^2\) wie folgt.
Finde den Punkt \(p_0 \in P\) mit minimaler \(y\)-Koordinate.
Lege eine horizontale Gerade durch \(p_0\) und rotiere sie gegen den Uhrzeigersinn um \(p_0\), bis sie einen anderen Punkt \(p_1 \in P\) trift. Rotiere die Gerade nun gegen den Uhrzeigersinn um \(p_1 \in P\)
usw., bis wieder \(p_0\) getroffen wird. Die getroffenen Punkte bilden den Rand von \(\CH (P)\).
Der Algorithmus kann auf \(\real ^3\) verallgemeinert werden.
Zeitaufwand: \(\O (n \cdot h)\) mit \(h\) der Anzahl der Punkte auf dem Rand von \(\CH (P)\)
Beweis: Der erste Schritt kostet Zeit \(\O (n)\), während jeder „Wickelschritt“ ebenfalls \(\O (n)\) kostet (minimaler Winkel finden). Man erhält also eine Gesamt-Laufzeit von \(\O (n \cdot h)\).
Der Algorithmus ist damit ausgabesensitiv. Wenn viele Punkte von \(P\) auf dem Rand von \(\CH (P)\) liegen, dann ist \(h \approx n\) und der Graham-Scan-Algorithmus ist dann schneller. Gilt allerdings \(h = o(\log n)\), so
ist der Gift-Wrapping-Algorithmus vorzuziehen.
Chans Algorithmus
Chans Algorithmus ist eine Kombination des Graham-Scan- (oder jedes anderen \(\O (n \log n)\)-Konvexe-Hülle-Alg.) und des Gift-Wrapping-Alg. Der Algorithmus hat zwar eine bestmögliche Laufzeit von \(\O
(n \log h)\), kann aber ohne Weiteres nicht auf \(\real ^3\) verallgemeinert werden.
Er benötigt zwar zunächst die Anzahl \(h\) der Punkte auf dem Rand von \(\CH (P)\), allerdings kann dieses Problem später umgangen werden.
Chans Algorithmus: Chans Algorithmus findet die konvexe Hülle in \(\real ^2\) wie
folgt.
Sei \(h \in \natural \) gegeben.
Partitioniere \(P\) in \(\frac {n}{h}\) Gruppen \(P_1, \dotsc , P_{n/h}\) zu je \(h\) Punkten.
Berechne die Mini-CHs \(\CH (P_i)\) für alle \(i = 1, \dotsc , \frac {n}{h}\) mittels des Graham-Scan-Alg.
Führe Gift-Wrapping über die Mini-CHs durch, allerdings mit maximal \(h\) Wickelschritten:
Finde den Punkt \(p_0 \in P\) mit minimaler \(y\)-Koordinate.
Bestimme die Rechtstangente durch \(p_0\) an jede Mini-CH und die zugehörigen Berührpunkte (\(\frac {n}{h}\) Stück).
Wähle den Berührpunkt mit dem kleinsten Winkel zu \(p_0\) (wie bei Gift-Wrapping).
Wähle diesen Punkt als neuen Basispunkt und iteriere, allerdings \(\le h\) mal. Ist nach \(h\) Iterationen \(p_0\) immer noch nicht erreicht, dann breche ab und gebe einen Fehler zurück.
Zeitaufwand für geg. \(h\): \(\O (n \log h)\)
Beweis: Schritte (1) und (2) kosten \(\O (n)\) bzw. \(\frac {n}{h} \cdot \O (h \log h) = \O (n \log h)\). Bei Schritt (3) werden \(\le h\) Wickelschritte durchgeführt.
Ein naives Berechnen der Rechtstangente würde bei jedem Wickelschritt \(\O (n)\) kosten, indem man jeden der \(n\) Eckpunkte der Mini-CHs anschaut (im schlechtesten Fall liegen alle Punkte auf den
Rändern der Mini-CHs).
Es geht aber schneller: Wenn man nur eine einzelne Mini-CH \(\CH (P_i)\) betrachtet, dann fällt auf, dass der berechnete Berührpunkt mit kleinstem Winkel zum aktuellen Punkt nur ein Mal um das Polygon
laufen kann. Es reicht also aus, sich den letzten Berührpunkt von \(\CH (P_i)\) zu merken und beim Ermitteln des Berührpunkts beim nächsten Wickelschritt nur die nächsten Eckpunkte von
\(\CH (P_i)\) zu betrachten. Für die Ermittlung der Berührpunkte von \(\CH (P_i)\) benötigt man so insgesamt nur \(\O (h)\) Schritte (so viele Eckpunkte kann \(\CH (P_i)\) höchstens
haben). Für alle Mini-CHs erhält man so die Laufzeit von \(\frac {n}{h} \cdot \O (h) = \O (n)\) (für Schritt (3)).
Der Algorithmus terminiert erfolgreich genau dann, wenn er mit \(h \ge h^\ast \) aufgerufen wurde (mit \(h^\ast \) der wahren Anzahl der Eckpunkte der konvexen Hülle \(\CH (P)\)). Zur Bestimmung von \(h^\ast
\) versucht man den Algorithmus daher zunächst mit \(h_1 := 4\), \(h_2 := 16\), \(h_3 := 256\) usw. (\(h_i := 2^{2^i}\)), bis bei \(h_j\) der Algorithmus erfolgreich terminiert hat.
Zeitaufwand für unbek. \(h^\ast \): \(\O (n \log h^\ast )\)
Beweis: Der \(i\)-te Aufruf kostet Zeit \(\O (n \log h_i)\), daher erhält man insgesamt den Zeitaufwand \(\sum _{i=1}^j \O (n \log h_i) = \O (n \cdot \sum _{i=1}^j 2^i) = \O (n \cdot 2^j) =
\O (n \log h_j)\). Wegen \(h_{j-1} < h^\ast \) (sonst hätte der Algorithmus schon bei \(j - 1\) erfolgreich terminiert) gilt allerdings \((h_{j-1})^2 = h_j < (h^\ast )^2\) und somit \(\log h_j < 2
\log h^\ast \) sowie \(\O (n \log h^\ast )\) Gesamt-Zeitaufwand.
RIC-Algorithmus
Der RIC-Algorithmus (engl. randomized incremental construction) ist ein sog. inkrementeller Algorithmus. Bei diesen wird die Lösung der ersten \(i\) Objekte
sukzessive für \(i = 1, \dotsc , n\) aus der Lösung der ersten \(i - 1\) Objekte berechnet. Die Invariante beim RIC-Algorithmus ist daher, dass im \(i\)-ten Schritt die konvexe Hülle von \(p_1,
\dotsc , p_i\) berechnet wird. Zusätzlich ist der Algorithmus randomisiert, d. h. der Algorithmus macht sein Vorgehen an bestimmten Stellen vom Zufall
abhängig.
RIC-Algorithmus: Der RIC-Algorithmus findet die konvexe Hülle in \(\real ^2\) wie folgt.
Permutiere \(P\) zufällig zu \(p_1, \dotsc , p_n\).
Berechne \(\CH _3 := \CH (p_1, p_2, p_3)\) als Dreieck \(\Delta p_1 p_2 p_3\) und berechne den Schwerpunkt \(m\).
Für \(i = 4, \dotsc , n\) weise jedem Punkt \(p_i\) die Kante des Dreiecks \(\CH _3\) zu, die sich mit \(\overline {mp_i}\) schneidet (gibt es keinen solchen Schnittpunkt, dann liegt \(p_i\) in \(\CH
_3\) und braucht nicht weiter betrachtet zu werden). Außerdem weise jeder Kante von \(\CH _3\) die Punkte zu, die auf die Kante verweisen.
Für \(i = 4, \dotsc , n\) wiederhole:
Starte bei der Kante, auf die der Punkt \(p_i\) zeigt.
Gehe nun in beide Richtungen auf dem Rand von \(\CH _{i-1}\) und bestimme so die beiden Tangenten an \(\CH _{i-1}\) durch \(p_i\). Alle übersprungenen Kanten werden gelöscht und die
zwei Tangenten werden eingefügt, um \(\CH _i\) zu erhalten. Aktualisiere nun noch die Verweise der Punkte und der Kanten.
Der RIC-Algorithmus kann auch auf höhere Dimensionen erweitert werden (mittels Breitensuche). Für \(d\) Dimensionen besitzt er eine Laufzeit von \(\O (n^{\lfloor d/2 \rfloor } \log n)\).
Laufzeit: Im Worst-Case kann die Laufzeit \(\Omega (n^2)\) sein. Die Bestimmung der Tangenten kostet zwar insgesamt nur \(\O (n)\) (jede übersprungene Kante wird gelöscht und es gibt
höchstens \(2n\) Kanten, für jeden Punkt zwei). Allerdings kann es für jedes \(i\) nötig sein, die Verweise aller verbleibenden Punkte zu aktualisieren (z. B. wenn alle Punkte
übereinander liegen, außer drei unten als Dreieck, und die Punkte von unten nach oben durchnummeriert werden), was in einer Laufzeit von \(\Omega (n^2)\) resultiert. Dieser Fall tritt aber nur bei bestimmten
Permutationen auf. Man kann zeigen, dass allermeistens günstigere Reihenfolgen gewählt werden. Dazu ermittelt man den Durchschnitt (Erwartungswert) der Laufzeiten über alle möglichen
Permutationen, die sog. erwartete Laufzeit.
erwartete Laufzeit: \(\O (n \log n)\)
Beweis: Sei \(T_j\) die erwartete Anzahl, die angibt, wie oft der Verweis des \(j\)-ten Punkts der zufälligen Permutation auf eine Kante während der Einfügung von \(p_4, \dotsc ,
p_{j-1}\) geändert werden musste (dabei ist \(j\) fest). Wenn man zeigen kann, dass \(T_j = \O (\log n)\) gilt, dann folgt die Behauptung, da die Gesamtlaufzeit dann \(\sum _{j=4}^n T_j = \O (n \log n)\)
beträgt.
Dazu verwendet man die Technik der Rückwärtsanalyse: Sei \(P_{i,j}\) für \(i < j\) die Wahrscheinlichkeit, dass der Verweis von \(p_j\) auf
eine Kante bei der Einfügung von \(p_i\) geändert werden musste. Dann gilt \(T_j = \sum _{i < j} P_{i,j}\) (denn wenn der Verweis geändert werden musste, entstehen Kosten von \(1\),
sonst \(0\)). Der Verweis von \(p_j\) auf eine Kante musste bei der Einfügung von \(p_i\) geändert werden genau dann, wenn die Kante, auf die \(p_j\) zeigt, nach dem Einfügen von \(p_i\) den
Punkt \(p_i\) als einen Endpunkt hat. Es gibt \(i\) mögliche Endpunkte \(p_1, \dotsc , p_i\), damit ist die Wahrscheinlichkeit, dass einer der beiden Endpunkte \(p_i\) ist, gleich \(P_{i,j} = \frac {2}{i}\) und
man erhält \(T_j = \sum _{i < j} \frac {2}{i} = \O (\log n)\).