Back to search

University of British Columbia

On fully characterizing terrain visibility graphs

Abstract

dc:description

A terrain is an x-monotone polygonal line in the xy-plane. Two vertices of a terrain are mutually visible if and only if they are adjacent or the line segment that connects them lies above the terrain (except at its endpoints). A graph whose vertices represent terrain vertices and whose edges represent mutually visible pairs of terrain vertices is called a terrain visibility graph. Understanding the graph theoretic properties of all terrain visibility graphs may help us understand the combinatorial structure of these geometric objects and help to address problems related to geometric visibility. The properties that are true of all terrain visibility graphs are called necessary properties. The set of properties that, if true, imply that a graph is a terrain visibility graph is called a sufficient set. We would like to find properties that are both necessary and sufficient; that is, we would like to characterize, graph theoretically, terrain visibility graphs. Abello et al. [Discrete and Computational Geometry,14(3):331–358,1995] studied the core induced subgraphs of the visibility graphs of staircase polygons, which are exactly the class of terrain visibility graphs. They showed that the visibility between vertices in such structures implies some ordering requirements on the slopes of the lines that connect pairs of vertices in any realization. They approached the problem of whether certain graph properties are sufficient by creating a slope order on the lines that connect all pairs of polygon vertices (in a possible realization) such that the slope order is consistent with the desired visibility graph. The main contribution of our work is to give a much simpler proof that these properties guarantee such a slope ordering. Our proof consequently gives a faster algorithm for constructing this slope order. Our approach attempts to clarify the implications of the graph theoretic properties on the ordering of the slopes, and may be interpreted as defining properties on an underlying oriented matroid.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Saeedi Bidokhti, Noushin

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/41902

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Saeedi Bidokhti, Noushin. On fully characterizing terrain visibility graphs. master's thesis, University of British Columbia, 2012. http://hdl.handle.net/2429/41902