TESSELLATIONS

FredericPaikSchoenbergDepartmentofStatistics

UniversityofCalifornia,LosAngeles

Atessellationmaybedefinedasadivisionofaspaceintoconvexpolyg-onalregions;divisionsoftheplane(R2)aremostoftendiscussed.Whilegeometristscenturiesagoreservedthetermtessellationmerelyfordivisionsoftheplaneintoregularpolygonsofequalsize,mostauthorsnowdefinetes-sellationsverybroadlysoastoincludeanyarrangementsofnon-overlappingshapescoveringRd,aswellaspartitionsofothermetricspaces.

Tessellationsarisequitenaturallyinnumerousapplications.Insomesit-uations,e.g.ingeography,cellularbiologyorcrystallography,onemaywishtodescribeobservedstructuresusingmodelsfortessellations.Inmanyotherapplications,pointprocessdataareobservedfromwhichonemaywishtocharacterizethemosaicofregionalpatterns.TheVoronoitessellationanditsdualconcept,theDelaunaytessellation,arecommonlyusedinsuchcircum-stances.Chapter1.2of[14]providesasurveyofthehistoricaldevelopmentofVoronoidiagramsandDelaunaytessellations,includingearlyapplications

1

indiversefieldssuchascrystallography,ecology,meteorology,epidemiology,linguistics,economics,archaeology,andastronomy,datingbacktoDescartesintheearly17thcentury.Referencestonumerousfurtherexamplesaregiveninchapter10.2of[17],includingexamplesinforestry,communicationthe-ory,geology,metallography,andzoology,andchapter5.3of[14]summarizesrecentapplicationsinawidevarietyofdisciplines.

VORONOITESSELLATIONS

AclassicexampleofarandomlygeneratedtessellationistheVoronoites-sellation(alsoassociatedwiththenamesDirichletandThiessen),whichsep-aratesaregionintocells{Di}usingapointprocessN.

(Figure1here)

TheVoronoitessellationisconstructedasfollows:foreachpointτiofthepointprocess,letDibetheareaconsistingofalllocationsinthespacewhich

2

areclosertoτithantoanyotherpointofN.ThisdefinitionisapplicabletoVoronoitessellationsinanymetricspace.AnexampleinR2isdepictedinFigure1.Attentionisusuallyrestrictedtonon-degeneratecasestoensurethattheVoronoitessellationresultingfromapointpatterniswelldefined.Forexample,onetypicallyassumesthatthereareatleasttwopoints,thatthepointsarealldistinct,andthatthereareonlyfinitelymanyinanyboundedregion.

GreenandSibson[3]providethefollowingdelightfullyintuitivedescrip-tion:“Onemightthinkofthepointsasbeingthelocationsofthelairsofcompetitivepredatorsofequalstrength;theregionassociatedwitheachpointisthentheareaavailabletothecorrespondingpredator.”Voronoitessella-tionshavethusbeenappliedinmodelsforpopulationsofspeciessuchasplantsandbirds(seee.g.chapter8.6of[15]).

CertaingeometricpropertiesoftheVoronoitessellationinRdareimme-diate.Forinstance,foranytwoadjacentcellsDiandDjcontainingpointsτiandτj,thesidecommontobothcellsisaperpendicularbisectorofthe

3

pointsτiandτj.Anotherexampleisthateachvertexisthecircumcenterofthepointswhosecellssharethevertex.Furtherexamplesofgeneralproper-tiesofVoronoitessellationsarediscussedinchapter2.3of[14].

AspecialcaseisthePoisson-Voronoitessellation,whichissimplyaVoronoitessellationgeneratedfromaPoissonprocess[seepointprocesses].ThePois-sonprocessgeneratingthetessellationisgenerallyassumedtobestationary,withrateλ.Manypropertiesofthe(stationary)Poisson-Voronoitessellationhavebeendiscovered:intheplanarcase,theexpectednumberofvertices(oredges)inanarbitraily-chosencell(e.g.thecellcontainingtheorigin)is6,anditsexpectedareais1/λ,forexample.AnexcellentsurveyoftheseandsimilarresultsforPoisson-VoronoitessellationsinRdisgivenin[10];alsoseechapter10.6of[17]andchapters5.2and5.5of[14].Poisson-Voronoitessellationsonthespherearediscussedin[1]and[9].

Voronoitessellationsoriginatingfromnon-Poissonpointprocesseshavealsobeeninvestigated.ForinstancethepointprocessNmaybemodeledascompoundPoisson,clustered,etc.Asurveyofresultsonplanarandspatial

4

tessellationsgeneratedbyvariousspecialnon-Poissonpointprocessesisgiveninchapter5.12of[14].

GreenandSibson[3]provideanefficientcomputeralgorithmforcon-structingaVoronoitessellationfromapointpattern.Seechapter4of[14]andreferencesthereinforadescriptionandcomparisonoftheGreen-Sibsonandalternativeconstructionmethods.Thesealgorithms,inconjunctionwithefficientroutinesforsimulatingpointprocesses(e.g.[6,13]),makesimulatingaVoronoitessellationasimpleandspeedytask.

DELAUNAYTESSELLATIONS

Givenapointprocesswithpoints{τi},analternativetypeoftessellationcanbeformedbyjoiningallneighboringpoints;by“neighboring”wemeanpairsofpointswhosecellsintheVoronoitessellationshareanedge.Thetes-sellationresultingfromthisconstructionistheDelaunaytessellation.Undergeneralconditions(seechapter2.3of[14]),thecellsofaplanarDelaunaytessellationaretriangular.TheDelaunaytessellationisalsocalledthedual

5

oftheVoronoitessellation.NotethatliketheVoronoitessellation,thedef-initionoftheDelaunaytessellationappliesnotmerelytoRdbuttogeneralmetricspaces.

WhenthepointprocessinthisconstructionisastationaryPoissonprocess,theresultiscalledaPoisson-Delaunaytessellation.PropertiesofPoisson-Delaunaytessellationsareverywell-known;forinstanceintheplanarcasethedensityfunctioncorrespondingtothetypicalcell,intermsofitssizeandangles,hasbeenderived[5,8].Chapter5.11of[14]providesanicesummaryofsuchproperties,includingresultsforPoisson-DelaunaytessellationsonRd.

JOHNSON-MEHLTESSELLATIONS

AnotherimportanttypeoftessellationistheJohnson-Mehltessellation,whichisderivedfromadynamic(e.g.spatial-temporal)pointprocessN.Supposethat,afteritisgenerated,eachpointofNisperceivedtogrowineverydirection,withsomeconstantspeed.Toapointinthepointprocess,therecorrespondsacellconsistingofallspatiallocationsfirsthitbythe

6

growthofthispoint.TheJohnson-Mehltessellationisthecollectionofthesecells.

InthespecialcasewherethepointsofNalloccuratexactlythesametime,theJohnson-MehltessellationreducestoaVoronoitessellation.Ingeneral,however,Johnson-Mehltessellationsmaybequitecomplex,contain-ingcellsthatarenotconvex,forinstance.Okabeetal.[14]notethattheJohnson-MehltessellationisaspecialcaseofanadditivelyweightedVoronoitessellation,inwhichtheweightassociatedwitheachpointτiissimplythetimetiatwhichthepointoccurs.

Well-writtentreatmentsofpropertiesofJohnson-Mehltessellationsaregivenin[11,12].Forfurtherreferencesonpropertiesandapplicationsinvar-iousfieldsincludingcrystallography,metallurgyandbiology,seepage314of[17]orchapter5.8of[14].

HYPERPLANETESSELLATIONS

7

AnimportanttypeoftessellationinRdisthehyperplanetessellation,i.e.thetessellationgeneratedbydividingupRdvia(d−1)-dimensionalhyper-planes.Forinstance,onemaydividetheplaneupintocellsusingarandomcollectionoflines.

Animportantmodelforarandomcollectionoflinesintheplaneisthe(undirected)PoissonlineprocessinR2,whichmaybedefinedasaPoissonpointprocessonthespaceR×(0,π],withtheconventionthatanypoint(t,θ)inR×(0,π]correspondstothelineinR2whoseperpendiculardistancefromtheoriginistandwhoseanglewiththex-axis,measuredcounterclockwise,isθ.NotethatthespaceR×(0,π]representsthehalf-cylinderofunitradiusinR3;seechapter8.2of[17]forelaboration.

ThedefinitionofthePoissonlineprocessextendsreadilytothePoissonhyperplaneprocesses,whichgeneratethePoissonhyperplanetessellations.PropertiesofPoissonlinetessellationsandPoissonplanetessellationsaresummarizedinchapter10.5of[17]andpage40of[14].Forexamplesofothertypesofhyperplaneprocesses,seepages250-255of[17].

8

FURTHERTESSELLATIONS

ThedefinitionoftheVoronoitessellationhasbeenextendedinvariousways.AnimportantexampleistheweightedVoronoitessellation,whichisthetessellationresultingfromtheconstructionidenticaltothatoftheordi-naryVoronoitessellationexceptthatinsteadofEuclideandistance,adifferentmetric(ornon-metricfunction)isused.ForexamplethedistancefunctionusedmaybeamultipleofEuclideandistance,i.e.thedistancebetweenanarbitrarylocationxandapointτiofthegeneratingpointprocessNmaybegivenbywid(x,τi),whereddenotesEuclideandistance,andwiisascalarthatdependsoni.TheresultingtessellationiscalledamultiplicativelyweightedVoronoitessellation.Alternatively,onemayconstructanadditivelyweightedVoronoitessellation,usingadistancefunctionoftheformwi+d(x,τi).Forfurtherexamplesofsuchtessellationsandtheirapplications,seechapter3.1of[14].

AnotherimportantgeneralizationoftheVoronoitessellationistheorder-k

9

Voronoitessellation,inwhichacellconsistsnotofalllocationsclosertoasinglepointτiofthepointprocessNthantoanyotherpointτj,butofalllocationsclosertoeachofthekpoints{τi1,...,τik}thantoanyotherpointofN.AlternativelyonemaymodifytheconstructionoftheVoronoitessel-lationbyprescribingthatcelliconsistoflocationsforwhichpointτiiskth(ratherthanfirst)inthelistofdistancesfromthepointsofNtothatloca-tion,orinthecasewhereNcontainsfinitelymanypoints,thatcelliconsistofalllocationsfurthestfrom(ratherthanclosestto)pointτi.ForpropertiesoftheseandotherextensionsoftheVoronoitessellation,seechapter3of[14].

AconstructcloselyrelatedtotheJohnson-MehltessellationisthedeadleavestessellationofMatheron[7],inwhichrandomshapesareplacedintheplane(orhigher-dimensionalspace)andcenteredatpoints{τi}ofastation-aryspatial-temporalPoissonprocess,withtheconventionthatiftwoshapesoverlap,thelatershapesupercedesthepriorone.See[2]andpages508-511of[16]forvariousproperties.Thecasewhereallthepointsτifallsimulta-neously,i.e.whererandomshapesareplacedwiththeircentersatthepointsofastationaryspatialPoissonprocess,iscalledaBooleanmodel.Typically

10

fortheBooleanmodel,oneallowsalltheshapestooverlapandinvestigatesthepropertiesofclumps,definedasconnectedclustersofoverlappingshapes.See[4],chapter13Bof[16]orchapter3of[17]forpropertiesandstatisticsfortheBooleanmodel.

11

References

[1]Arbeiter,E.,andZ¨ahle,M.(1994).Geometricmeasuresforrandommosaics

insphericalspaces.StochasticStochasticsRep.46,63-77.

[2]Cowan,R.,andTsang,A.(1994).Thefalling-leavesmosaicanditsequilib-riumproperties.Adv.Appl.Prob.26,54-62.

[3]Green,P.,andSibson,R.(1978).ComputingDirichlettessellationsinthe

plane.ComputerJournal21,168-173.

[4]Hall,P.(1986).Clumpcountsinamosaic.Ann.Probab.14,424-458.[5]Kendall,D.(1983).TheshapeofPoisson-Delaunaytriangles.InStudiesin

ProbabilityandRelatedTopicsinHonourofOctavOnicescu,M.C.Deme-trescuandM.Iosifescu,eds.Nagard,Montreal,pp.321-330.

[6]Lewis,P.,andShedler,G.(1979).SimulationofnonhomogeneousPoisson

processesbythinning.NavalResearchLogisticsQuarterly26,403-413.[7]Matheron,G.(1968).Sch´emabool´eens´equentialdepartitional´eatoire.Tech.

ReportN-83,EcoledeMinesdeParis.

[8]Miles,R.(1970).OnthehomogeneousplanarPoissonprocess.Math.Biosci.

6,85-127.

12

[9]Miles,R.(1971).Randompoints,sets,andtessellationsonthesurfaceofa

sphere.SankyaA33(2),145-174.

[10]Miles,R.(1972).Therandomdivisionofspace.Suppl.Adv.Appl.Prob.,

243-266.

[11]Møller,J.(1992).RandomJohnson-Mehltessellations.Adv.Appl.Prob.

24,814-844.

[12]Møller,J.(1995).GenerationofJohnson-Mehlcrystalsandcomparative

analysisofmodelsforrandomnucleation.Adv.Appl.Prob.27,367-383.[13]Ogata,Y.(1981).OnLewis’simulationmethodforpointprocesses.IEEE

Trans.Inf.TheoryIT-27,23-31.

[14]Okabe,A.,Boots,B.,Sugihara,K.,andChiu,S.(2000).SpatialTessella-tions,2nded.Wiley,Chichester.

[15]Ripley,B.(1981).SpatialStatistics.Wiley,NY.

[16]Serra,J.(1982).ImageAnalysisandMathematicalMorphology,vol.1.

AcademicPress,London.

[17]Stoyan,D.,Kendall,W.,andMecke,J.(1995).StochasticGeometryand

itsApplications,2nded.Wiley,Chichester.

13

Figure1:ConstructionofPoisson-Voronoitessellation

14

**************************************************V15

**************************************************|