Paper: Visibility Queries among Horizontal Segments

Visibility Queries among Horizontal Segments - A Dynamic Data Structure

Sergei Bespamyatnikh, Matthew J. Katz, Frank Nielsen and Michael Segal

Abstract:
Consider the following interactive computer game. A set of blue horizontal segments is drawn in a window. The player must draw in the window, within a few seconds, a red segment that is not visible from the bottom edge nor the top edge of the window's boundary. If the red segment drawn by the player is visible, then the player does not get any points for this move; otherwise, the number of points is proportional to the length of the segment. After computing the score for this move, the red segment is removed, and either a new blue segment is added to the scene or an existing blue segment is deleted from the scene. The player must now draw again a red segment for the new scene, get points for this move, and so on. The main algorithmic difficulty in the implementation of this game, is to determine at each round whether or not the red segment drawn by the player is visible from one of the horizontal edges of the window's boundary. We propose a data structure that overcomes this difficulty. More precisely, we consider the following problem.

Problem: Maintain a set S of horizontal segments in the plane under insertions and deletions, so that when given a query horizontal segment l, one can efficiently determine whether l is visible from the x-axis, in the sense that one can draw a vertical segment whose endpoints lie on the x-axis and on l, respectively, which does not intersect any of the segments in S. Our data structure for this problem is quite simple but new and neat. It is based on a segment tree. Its size is O(n log n), where n is the current size of S, and it supports logarithmic-time queries. An update, i.e., insertion or deletion, costs O(log² n).

Download the PDF paper here (121 KB size, 2 pages).

Bibtex entry:


@InCollection{bkns-vqhsds-2000 
	, author =  "Sergei Bespamyatnikh, Matthew J. Katz, Frank Nielsen and Michael Segal" 
	, title =   "Visibility Queries among Horizontal Segments - A Dynamic Data Structure" 
	, booktitle =   "Papers of the Japanese Conference on Discrete and Computational Geometry (JCDCG 2000), Tokai 
			University, Japan" 
	, publisher = "Tokai Proceedings" 
	, year =    2000 
	, pages =   "17--18" 
}

Related publication:

Sergei Bespamyatnikh, Matthew J. Katz, Frank Nielsen and Michael Segal,
Visibility Queries among Horizontal Segments - A Dynamic Data Structure,
Japan Conference on Discrete and Computational Geometry (JCDCG), booklet,
pp. 17-18, 2000.

Last updated, 2003.