Låt T vara ett rotat och vägt träd, där vikten av någon nod är lika med summan av vikterna av dess barn. Den populära Treemap algoritmen visualiserar ett träd som en hierarkisk partition av en kvadrat till rektanglar, där arean av rektangeln som motsvarar någon nod i T är lika med vikten av den noden. Rektanglarnas proportion i en sådan rektangulär partition beror nödvändigtvis på vikterna och kan bli godtyckligt hög. Vi introducerar ett nytt hierarkiskt partitionssystem, kallat en polygonal partition, som använder konvexa polygoner snarare än bara rektanglar. Vi presenterar två metoder för att bygga polygonala partitioner, båda med garantier på det värsta-case proportion av konstruerade polygoner; i synnerhet, båda metoderna garanterar en bunden på proportionen som är oberoende av vikterna av noderna. Vi anser också rektangulära partitioner med slack, där områdena i rektanglar kan skilja sig något från vikterna i motsvarande noder. Vi visar att detta gör det möjligt att erhålla partitioner med konstant proportion. Detta resultat generaliserar till hyper-rektangula partitioner i R d. Vi använder dessa partitioner med slack för att inbädda ultrametrics i d-dimensionella Euclidean utrymme: vi ger en polylog( på)-tillnärmning algoritm för inbäddning n-punkt ultrametrics i R d med minsta förvrängning, där  påvisar spridningen av metriska. Den tidigare mest kända approximation förhållandet för detta problem var polynomial i n. Detta är den första algoritmen för att inbädda en icke-trivial familj av viktade-grafmått i ett utrymme av konstant dimension som uppnår polylogaritmisk approximation förhållande.
De enda kända positiva resultaten är en O(1)-approximation algoritm för att inbädda undergrupper av 2-sfären i R 2 [5], och approximationsalgoritmer för inbäddning ultrametrics i R d [4, REF.
Fat Polygonal Partitions with Applications to Visualization and Embeddings
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}