2003 | OriginalPaper | Buchkapitel
Multi-way Space Partitioning Trees
verfasst von : Christian A. Duncan
Erschienen in: Algorithms and Data Structures
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we introduce a new data structure, the multi-way space partitioning (MSP) tree similar in nature to the standard binary space partitioning (BSP) tree. Unlike the super-linear space requirement for BSP trees, we show that for any set of disjoint line segments in the plane there exists a linear-size MSP tree completely partitioning the set. Since our structure is a deviation from the standard BSP tree construction, we also describe an application of our algorithm. We prove that the well-known Painter’s algorithm can be adapted quite easily to use our structure to run in O(n) time. More importantly, the constant factor behind our tree size is extremely small, having size less than 4n.