World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue: Selected Papers from the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006), 18–20 December 2006, Kolkata, IndiaNo Access

DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE

    https://doi.org/10.1142/S0218195909002861Cited by:22 (Source: Crossref)

    Given a triangulation G, whose vertex set V is a set of n points in the plane, and given a real number γ with 0 < γ < π, we design an O(n)-time algorithm that constructs a connected subgraph G' of G with vertex set V whose maximum degree is at most 14 + ⌈2π/γ⌉. If G is the Delaunay triangulation of V, and γ = 2π/3, we show that G' is a t-spanner of V (for some constant t) with maximum degree at most 17, thereby improving the previously best known degree bound of 23. If G is a triangulation satisfying the diamond property, then for a specific range of values of γ dependent on the angle of the diamonds, we show that G' is a t-spanner of V (for some constant t) whose maximum degree is bounded by a constant dependent on γ. If G is the graph consisting of all Delaunay edges of length at most 1, and γ = π/3, we show that a modified version of the algorithm produces a plane subgraph G' of the unit-disk graph which is a t-spanner (for some constant t) of the unit-disk graph of V, whose maximum degree is at most 20, thereby improving the previously best known degree bound of 25.

    This research was supported by the Natural Sciences and Engineering Research Council of Canada.

    References

    Remember to check out the Most Cited Articles!

    Check out these titles in image analysis!