AbstractConsiderabasestationinawirelesssensornetworkthatreceivesincominginputpointsandmustmaintainarun-ningconvexhullwithinamemoryconstraint. WegiveanewstreamingalgorithmthatprocesseseachpointintimeO(logk) wherekisthememoryconstraint,whilemaintaininganoptimalareaerrorofO1=k 2 .1 IntroductionA streaming algorithm is an on-line approximation al-gorithmconstrainedtoworkwithinamemorybudget.When more memory than the allowed budget is de-manded,wemustmakedecisionsonwhatisworthkeep-ingandwhatmustbediscarded. Astreamingalgorithmhas three parts: aninitializationprocedure, a process-ing algorithm for each successive input, and a facilityforansweringqueriesusingtherestrictedmemory.2 Related WorkPreparata gave an exact online algorithm [5] but withno memory constraints. The streaming algorithm pro-posed by Hershberger and Suri [1, 3, 2] maintains ex-treme points in kuniformly spaced directions and an-otherkextremepointsinadaptivelysampleddirections.Their algorithm has a distance error of O1=k 2 ; noareameasurewasreported.LopezandReisner[4]proposedanalgorithmforap-proximating an n-gon by a k-gon, k<n. Their algo-rithmbuildsaninscribedk-gonbyrepeatedlyremovingan ear of minimum area until only kvertices remain.(Anear ofaconvexpolygonisanytriangleformedbythree consecutive vertices.) However their algorithm,unlike ours, is not on-line, as all the vertices of the n-gonareknownaheadoftime.3 Streaming AlgorithmLet C = (p
['Raimi A. Rufai', 'Dana Richards']
A Streaming Algorithm for the Convex Hull