<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-158

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

M.S. Paterson and F.F. Yao, Optimal Binary Space Partitions for Orthogonal Objects (April 1, 1990).

Abstract

A binary space partition, or BSP is a scheme for recursively dividing a configuration of objects by hyperplanes until all objects are separated. BSPs are widely used in computer graphics as the underlying data structure for computations such as real-time hidden-surface removal, ray tracing, and solid modelling. In these applications, the computational cost is directly related to the size of the BSP, ie the toal number of fragments of the objects generated by the partition. Until recently, the question of minimizing the size of BSPs for given inputs had been studied only empirically. We concentrate here on ortogonal objects, a case which arises frequently in practice and deserves special attention. We construct BSPs of linear size for any set of orthogonal line segments in the plane. In three dimensions, BSPs of size O(n^1.5) for any set of n mutually orthogonal line segments or rectangles are constructed. These bounds are optimal and may be contrasted with the omega(n²) bound for general polygonal objects in R³.

<%@ include file="cited.html" %>

M.S. Paterson and F.F. Yao, "Optimal Binary Space Partitions for Orthogonal Objects", Journal of Algorithms 13, pp. 99-113 (1992)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>