Mixed Map Labeling

摘要

Pointfeaturemaplabelingisageometricvisualizationproblem,inwhichasetofinputpointsmustbelabeledwithasetofdisjointrectangles(theboundingboxesofthelabeltexts).Itispredominantlymotivatedbylabelplacementinmapsbutitalsohasothervisualizationapplications.Typically,labelingmodelseitheruseinternallabels,whichmusttouchtheirfeaturepoint,orexternal(boundary)labels,whichareplacedoutsidetheinputimageandwhichareconnectedtotheirfeaturepointsbycrossing-freeleaderlines.Inthispaperwestudypolynomial-timealgorithmsformaximizingthenumberofinternallabelsinamixedlabelingmodelthatcombinesinternalandexternallabels.Themodelrequiresthatallleadersareparalleltoagivenorientationθ∈[0,2π),thevalueofwhichinfluencesthegeometricpropertiesandhencetherunningtimesofouralgorithms.