No label defined (Q4277403)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 495506
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 495506

      Statements

      0 references
      0 references
      1 March 1995
      0 references
      computational geometry
      0 references
      trapezoidal decomposition
      0 references
      The paper studies the problem of partitioning a polygonal region in the plane into trapezoids (quadrilaterals with two horizontal sides). Since the computation of a minimum size partitioning is known to be intractable (NP-complete), the authors present a straightforward algorithm for a partitioning and they prove upper bounds on the ratio of the size of the obtained partitioning and the size of the minimum size partitioning. The algorithm is quite standard in computational geometry. Perhaps more interesting is the formula that expresses the size of the minimum size partitioning in the number of holes, connected components, and line segments in the boundary of the region. In computational geometry, such a partitioning is called a trapezoidal decomposition and algorithms for it have been given by \textit{A. Fournier} and \textit{D. Y. Montuno} [ACM Trans. Graphics 3, 153-174 (1984; Zbl 0592.68084)], \textit{K. L. Clarkson} and \textit{P. W. Shor} [Discrete Comput. Geom. 4, No. 5, 387-421 (1989; Zbl 0681.68060)], \textit{R. Seidel} [Comput. Geom.: 1, 51-61 (1991; Zbl 0733.68092)] and others.
      0 references

      Identifiers