Beta-skeletons have unbounded dilation. (English) Zbl 1006.65018
A number of authors have studied the question of dilation of various geometric graphs [see D. Eppstein in: Handbook of computational geometry, Chapter 9, 425-461 (2000; Zbl 0544.05021)]. The author studies here beta-skeletons [cf. R. C. Veltkamp, Comput. Geom. 1, No. 4, 227-246 (1992; Zbl 0748.68089)], which are of more recent interest. It is shown here that one can find point sets for which the beta-skeleton has arbitrarily high dilation. The construction given here uses fractal curves closely related to Koch snowflake.
Reviewer: H.P.Dikshit (New Delhi)
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Amenta, A. B.; Bern, M. W.; Eppstein, D., The crust and the \(β\)-skeleton: combinatorial curve reconstruction, Graphical Models Image Processing, 60/2, 2, 125-135 (1998) |
| [2] | Cheng, S.; Xu, Y., Approaching the largest \(β\)-skeleton within a minimum weight triangulation, (Proc. 12th Symp. Comp. Geom. (1996), ACM), 196-203 |
| [3] | Chew, L. P., There is a planar graph almost as good as the complete graph, (Proc. 2nd Symp. Comp. Geom. (1986), ACM), 169-177 |
| [4] | Chew, L. P., There are planar graphs almost as good as the complete graph, J. Comput. System Sci., 39, 205-219 (1989) · Zbl 0682.05032 |
| [5] | Das, G.; Joseph, D., Which triangulations approximate the complete graph?, (Proc. Int. Symp. Optimal Algorithms. Proc. Int. Symp. Optimal Algorithms, Lecture Notes in Comp. Sci., 401 (1989), Springer: Springer Berlin), 168-192 · Zbl 0704.68087 |
| [6] | Dobkin, D. P.; Friedman, S. J.; Supowit, K. J., Delaunay graphs are almost as good as complete graphs, Discrete Comput. Geom., 5, 399-407 (1990) · Zbl 0693.05045 |
| [7] | Eppstein, D., Spanning trees and spanners, (Handbook of Computational Geometry, Chapter 9 (2000), Elsevier: Elsevier Amsterdam), 425-461 · Zbl 0944.05021 |
| [8] | Gabriel, K. R.; Sokal, R. R., A new statistical approach to geographic variation analysis, Systematic Zoology, 18, 259-278 (1969) |
| [9] | Keil, J. M., Computing a subgraph of the minimum weight triangulation, Computational Geometry, 4, 13-26 (1994) · Zbl 0807.68100 |
| [10] | Keil, J. M.; Gutwin, C. A., The Delaunay triangulation closely approximates the complete Euclidean graph, (Proc. 1st Worksh. Algorithms and Data Structures. Proc. 1st Worksh. Algorithms and Data Structures, Lecture Notes in Comp. Sci., 382 (1989), Springer: Springer Berlin), 47-56 · Zbl 0766.52004 |
| [11] | Kirkpatrick, D. G.; Radke, J. D., A framework for computational morphology, (Computational Geometry (1985), North-Holland: North-Holland Amsterdam), 217-248 |
| [12] | Su, T.-H.; Chang, R.-C., The \(k\)-Gabriel graphs and their applications, (Proc. Int. Symp. Algorithms. Proc. Int. Symp. Algorithms, Lecture Notes in Comp. Sci., 450 (1990), Springer: Springer Berlin), 66-75 |
| [13] | Veltkamp, R. C., The \(γ\)-neighborhood graph, Computational Geometry, 1, 227-246 (1992) · Zbl 0748.68089 |
| [14] | Wang, C. A.; Yang, B., A tight bound for beta-skeleton of minimum weight triangulations, (Proc. 6th Int. Worksh. Algorithms and Data Structures. Proc. 6th Int. Worksh. Algorithms and Data Structures, Lecture Notes in Comp. Sci., 1663 (1999), Springer: Springer Berlin), 265-275 · Zbl 1063.68684 |
| [15] | Yang, B.-T., A better subgraph of the minimum weight triangulation, Inform. Process. Lett., 56, 255-258 (1995) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
