10
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      \(\beta\)-skeletons for a set of line segments in \(R^2\)

      Preprint
      ,

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          \(\beta\)-skeletons are well-known neighborhood graphs for a set of points. We extend this notion to sets of line segments in the Euclidean plane and present algorithms computing such skeletons for the entire range of \(\beta\) values. The main reason of such extension is the possibility to study \(\beta\)-skeletons for points moving along given line segments. We show that relations between \(\beta\)-skeletons for \(\beta > 1\), \(1\)-skeleton (Gabriel Graph), and the Delaunay triangulation for sets of points hold also for sets of segments. We present algorithms for computing circle-based and lune-based \(\beta\)-skeletons. We describe an algorithm that for \(\beta \geq 1\) computes the \(\beta\)-skeleton for a set \(S\) of \(n\) segments in the Euclidean plane in \(O(n^2 \alpha (n) \log n)\) time in the circle-based case and in \(O(n^2 \lambda_4(n))\) in the lune-based one, where the construction relies on the Delaunay triangulation for \(S\), \(\alpha\) is a functional inverse of Ackermann function and \(\lambda_4(n)\) denotes the maximum possible length of a \((n,4)\) Davenport-Schinzel sequence. When \(0 < \beta < 1\), the \(\beta\)-skeleton can be constructed in a \(O(n^3 \lambda_4(n))\) time. In the special case of \(\beta = 1\), which is a generalization of Gabriel Graph, the construction can be carried out in a \(O(n \log n)\) time.

          Related collections

          Most cited references9

          • Record: found
          • Abstract: not found
          • Article: not found

          A New Statistical Approach to Geographic Variation Analysis

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Finding the upper envelope of n line segments in O(n log n) time

              Bookmark
              • Record: found
              • Abstract: not found
              • Book Chapter: not found

              Straight skeletons for general polygonal figures in the plane

                Bookmark

                Author and article information

                Journal
                20 November 2014
                2015-08-12
                Article
                1411.5457
                f2364682-4e9b-4a9c-9624-a555b77f54b4

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                cs.CG

                Comments

                Comment on this article