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

Partitioning space for range queries

Tools
- Tools
+ Tools

Yao, F. Frances, Dobkin, David P., Edelsbrunner, Herbert and Paterson, Michael S. (1988) Partitioning space for range queries. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

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

Download (13Mb) | Preview

Request Changes to record.

Abstract

It is shown that, given a set S of n points in R3, one can always find three planes that form an eight-partition of S, that is, a partition where at most n/8 points of S lie in each of the eight open regions. This theorem is used to define a data structure, called an octant tree, for representing any point set in R3. An octant tree for n points occupies O(n) space and can be constructed in polynomial time. With this data structure and its refinements, efficient solutions to various range query problems in 2 and 3 dimensions can be obtained, including (1) half-space queries: find all points of S that lie to one side of any given plane; (2) polyhedron queries: find all points that lie inside (outside) any given polyhedron; and (3) circular queries in R2: for a planar set S, find all points that lie inside (outside) any given circle. The retrieval time for all these queries is T(n)=O(na + m) where a= 0.8988 (or 0.8471 in case (3)) and m is the size of the output. This performance is the best currently known for linear-space data structures which can be deterministically constructed in polynomial time.

Item Type: Report
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Partitions (Mathematics), Trees (Graph theory)
Series Name: Department of Computer Science research report
Publisher: University of Warwick. Department of Computer Science
Official Date: March 1988
Dates:
DateEvent
March 1988Completion
Number: Number 118
Number of Pages: 18
DOI: CS-RR-118
Institution: University of Warwick
Theses Department: Department of Computer Science
Status: Not Peer Reviewed
Publication Status: Unpublished
Reuse Statement (publisher, data, author rights): F.F.&nbsp;Yao, D.&nbsp;Dobkin, H.&nbsp;Edelsbrunner and M.S.&nbsp;Paterson, &ldquo;Partitioning Space for Range Queries&rdquo;, <i>SIAM Journal on Computation</i> <b>18</b>, pp.&nbsp;371-384 (1989)
Funder: Xerox Corporation, Science and Engineering Research Council (Great Britain) (SERC)
Related URLs:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

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