WorstCase Versus Average Case Complexity of RaySho

Worst-CaseVersusAverageCaseComplexityofRay-ShootingLaszloSzirmay-Kalos,GaborMartonDepartmentofControlEngineeringandInformationTechnology,TechnicalUniversityofBudapest,Budapest,M}uegyetemrkp.11,H-1111,[e-mail]:Thispaperexaminesworst-caseandaverage-casecomplexitymea-suresofray-shootingalgorithmsinordertondtheanswertothequestionwhycomputergraphicspractitionerspreferheuristicmethodstoextensivelystudiedworst-caseoptimalalgorithms.Itdemonstratesthatray-shootingrequiresatleastlogarithmictimeintheworst-caseanddiscussesthestrategieshowtodesignsuchworst-caseoptimalalgorithms.Italsoexaminesthelower-boundsofstoragecom-plexityoflogarithmic-timealgorithmsandconcludesthatlogarithmictimehasveryhighpriceintermsofrequiredstorage.Inordertondaverage-casemea-sures,aprobabilisticmodelofthesceneisestablished.Weconcludethatalgo-rithmsoptimizedfortheaverage-casearenotonlymuchsimplertoimplement,buthavemoderatestoragerequirementandcanevenrunfasterforthemajorityofproblems.1IntroductionComputergraphicsexaminesthelight-objectinteractionofsurfacesin3Dspace.Inordertodeterminethereectedlightofasurfacepoint,theobjectsthatradiatelightontothispointmustbeknown.Forasingledirection,thisrequirestheemanationofahalf-line|calledray|fromthesurfacepointandthecomputationoftheobjectthatisrstintersectedbythisray.1Thisfundamentalgeometricproblemiscalledray-shooting.Forthecompletesolutionoftherenderingproblem,alotofraysshouldbeshotandtraced,thusitisworthpreprocessingthesceneintoadatastructurethatmakesray-shootingmoreeective.Frompracticalpointofview,eectivesolutionmeansinventingtrickyalgorithmsanddemonstratingbysimulationthatthesealgorithmsarereallyfasterfortheexaminedtestcases.Fromtheoreticalpointofview,however,wemustformallyprovethatanalgorithmhasbettercomplexitycharacter-isticsthantheothers.Complexitymeasuresexpresstherateofincreaseoftherequiredtimeandmemoryspaceasthesizeoftheproblemgrows.Thesizeoftheproblemisthenumberoftheobjectsinthescenefortheray-shootingproblem.Inthispaperthenumberofobjects,computationtimeandrequiredstoragearedenotedbylettern,T(n)andS(n)respectively.ThetimeandspacecomplexitiesimposeconstraintsonthefunctionsT(n)andS(n).Afunctiong(n)issaidtobeinO(f(n))ifthereexistpositivecon-stantscandNsothatg(n)cf(n)ifnN.ThusnotationOdescribesanupperbound.Notation,ontheotherhand,denesalowerbound:afunctiong(n)isin(f(n))ifthereexistpositiveconstantscandNsothatg(n)cf(n)ifnN.Finally,ifg(n)isbothinO(f(n))andin(f(n)),theng(n)issaidtobein(f(n)).Themainobjectiveofcomplexityanalysisistondalgorithmsthathavereasonableresourcerequirementsinthisasymptoticsense.Therequiredtimeisexpressedbythenumberofconstanttimeoperationsneededtocompletethealgorithm.Beforecarryingoutsuchananalysis,wehavetodenewhatkindofoperationscanbeusedtodenethealgorithm.Inthegenerallyacceptedalgebraicdecisiontreemodel,thefollowingoperationtypeisallowed:analgebraicfunctionisevaluatedandaccordingtoitsresultadeci-sionismadetoselectthenextoperation.Inthisframework,thecomputationcanbevisualizedbyabinarytreethatisdividedintotwobranchesbyeverysingledecision(thisiswhythemodeliscalledthealgebraicdecisiontreemodel).Intheclassicalapproachalgorithmsareoptimizedfortheworstcase,thuscomplexitymeasuresalsoexpresstheresourcerequirementsoftheworstarrangementofinputofagivensize.Thustheworst-casecomplexitymeasureis:T(n)=maxo1;:::;on2Otn(o1;:::;on);(1)2whereoirepresentstheparametersetdeningobjectiinthescene.Thevectoro1;:::;onofobjectparametersrepresentstheinputofthealgorithmandisalsocalledtheinputconguration.Worst-casecomplexitymeansthatthecomputationtimeandspacemustbebelowthegivenlimitsforanyinputcongurationofgivensize.Computergraphicsalgorithmsoptimizedfortheworstcasewereusuallybornintheframeworkofcomputationalgeometrywhichworkswithconstructssuchashyperplanes,cuttings,etc.,thusitusuallyrestrictsthetypeofobjectstothosethatareboundedbyplanarfaces.Thepracticeofcomputergraphics,ontheotherhand,hasproduceditsowntechniques,thatcanbecalledheuristicmethods.Theseheuristicmethodsdonotaimatworst-caseoptimizationbutratheraimatoptimizingfortheaveragecase.Intheframeworkofaveragecasecomplexityevaluation,algorithmsareoptimizedforthemajorityofthepossibleinputsnotfortheworstofthem.Moreprecisely,thecomplexitymeasurewillbetheexpectedvalueoftherunningtimeinsteadofthemaximumrunningtime.Iftheso-lutionforaninputcongurationtakesverylongtime,butthiscongurationhasveryloworevenzeroprobability,thenthisdoesnotmaketoomuchdierenceintheaveragecasecomplexityofthealgorithm.Thusthedenitionoftheaverage-casecomplexitymeasureis:T(n)=E[tn]=Zo12OZon2Otn(o1;:::;on)fn(o1;:::;on)do1don;(2)whereoiistheparametersetofobjectiasbeforeandfnistheprobabilitydensityofthepossibleinputcongurations.Thenaivesolutionoftheray-shootingproblem,wheneachobjectistriedtobeintersected,andthenthenearestintersectionisretained,requiresob-viouslylineartimebothintheworst-caseandintheaverage-case.However,havingpreprocessedtheobjectspaceintoasophisticateddatastructure,thisproblemcanbesolvedmoreeectively.2PreviousworkOneofth