×

A tight lower bound on the size of visibility graphs. (English) Zbl 0637.68076

The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. The article proves that the visibility graph of n nonintersecting line segments has at least 5n-4 edges. This lower bound is tight.
The result is of some interest in connection with the following problem: Is there an algorithm for constructing the visibility graph which takes less than \(\Omega\) (n 2) time if the number of edges of this graph is subquadratic?
Reviewer: H.-D.Hecker

MSC:

68R99 Discrete mathematics in relation to computer science
68R10 Graph theory (including graph drawing) in computer science
62C25 Compound decision problems in statistical decision theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asano, Ta.; Asano, Te.; Guibas, L. J.; Hershberger, J.; Imai, H., Visibility of disjoint polygons, Algorithmica, 1, 49-63 (1986) · Zbl 0611.68062
[2] Edelsbrunner, H.; Guibas, L. J., Topologically sweeping an arrangement, Proc. 18th Ann. ACM Symp. on Theory of Computing, 389-403 (1986)
[3] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, Proc. 25th Ann. IEEE Symp. on Foundations of Computer Science, 338-346 (1984)
[4] Lee, D. T., Proximity and reachability in the plane, (Ph.D. Thesis (1979), Dept. of Electrical Engineering, Univ. of Illinois: Dept. of Electrical Engineering, Univ. of Illinois Urbana-Champaign)
[5] R. Pollack and E. Welzl, Private communication.; R. Pollack and E. Welzl, Private communication.
[6] Sharir, M.; Schorr, A., On shortest paths in polyhedral spaces, Proc. 16th Ann. ACM Symp. on Theory of Computing, 144-153 (1984)
[7] Welzl, E., Constructing the visibility graph for n line segments in \(O(n^2)\) time, Inform. Process. Lett., 20, 167-171 (1985) · Zbl 0573.68036
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.