Increasing-Chord Graphs On Point Sets
Dehkordi, Hooman Reisi
Computer Science - Computational Geometry | Computer Science - Discrete Mathematics
arxiv: Computer Science::Sound
acm: MathematicsofComputing_DISCRETEMATHEMATICS | TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
We tackle the problem of constructing increasing-chord graphs spanning point sets. We prove that, for every point set P with n points, there exists an increasing-chord planar graph with O(n) Steiner points spanning P. Further, we prove that, for every convex point set P with n points, there exists an increasing-chord graph with O(n log n) edges (and with no Steiner points) spanning P.