Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Binary partitions with applications to hidden-surface removal and solid modelling

Tools
- Tools
+ Tools

Paterson, Michael S. and Yao, F. Frances (1989) Binary partitions with applications to hidden-surface removal and solid modelling. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)

[img]
Preview
PDF
WRAP_cs-rr-139.pdf - Requires a PDF viewer.

Download (13Mb) | Preview

Request Changes to record.

Abstract

We consider schemes for recursively dividing a set of geometric objects by hyperplanes until all objects are separated. Such a binary partition is naturally considered as a binary tree where each internal node corresponds to a division and the leaves correspond to the resulting fragments of objects. The goal is to choose the hyperplanes properly so that the size of the binary partition, i.e., the number of resulting fragments of the objects, is minimized. We construct binary. partitions of size 0(n log n) for n edges in the plane, and of size 0(n) if the edges are orthogonal. In three dimensions, we obtain binary partitions of size 0(n2) for n planar facets, and prove a lower bound of Q(nT). Two applications of efficient binary partitions are given. The first is an 0(n2 )-sized data structure for implementing a hidden-surface removal scheme of Fuchs, Kedem and Naylor [5]. The second application is in solid modelling: given a polyhedron described by its n faces, we show how to generate an 0(n2 )-sized CSG (constructive-solid-geometry) formula whose literals correspond to halfspaces supporting the faces of the polyhedron (see Peterson [9] and Dobkin et al. [3]). The best previous results for both of these problems were 0(n3).

Item Type: Report
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Computer graphics
Series Name: Department of Computer Science Research Report
Publisher: University of Warwick. Department of Computer Science
Place of Publication: Coventry, UK
Official Date: March 1989
Dates:
DateEvent
March 1989Completion
Number: Number 139
Number of Pages: 18
DOI: CS-RR-139
Institution: University of Warwick
Theses Department: Department of Computer Science
Status: Not Peer Reviewed
Publication Status: Unpublished
Reuse Statement (publisher, data, author rights): M.S.&nbsp;Paterson and F.F.&nbsp;Yao, &ldquo;Efficient Binary Partitions for Hidden-Surface Removal and Solid Modeling&rdquo;, <i>Discrete and Computational Geometry</i> <b>5</b>, pp.&nbsp;485-503 (1990)
Related URLs:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us