2013/01/15 by Fatemeh Rajabi-Alni, Rajabi-Alni, Fatemeh, Alireza Bagheri +1
Computer Science · Engineering · Environmental Science · #3D Modeling in Geospatial Applications #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Remote Sensing and LiDAR Applications
paper · pdf · doi:10.48550/arxiv.1301.3471
openalex publication_date 2013/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an undirected planar graph G with n vertices and a set S of n points inside a simple polygon P, a point-set embedding of G on S is a planar drawing of G such that each vertex is mapped to a distinct point of S and the edges are polygonal chains surrounded by P. A special case of the embedding problem is that in which G is a balanced binary tree. In this paper, we present a new algorithm for embedding an n-vertex balanced binary tree BBT on a set S of n points bounded by a simple m-gon P in O(m2 + n(log n)2 + mn) time with at most O(m) bends per edge.