Publisher's Synopsis
Excerpt from Robotic Research Technical Report: On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottman Line Sweeping Algorithm
We also consider a weaker variant of the problem (which has nothing to do with the bentley-ottman algorithm), in which we are given an arbitrary collection of n segments and wish to estimate the number of pairs of non-intersecting vertically visible segments, dropping the condition that these pairs intersect when extended to the right (and that the segments all have to end on the same vertical line). We show that the number of these pairs in this gen eral case is and can be ?(u4'3) in the worst case. (thus the innocent looking extra conditions that are assumed in the bentley-ottman case appear to be crucial for.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.