LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Yao, F. Frances; Dobkin, David P.; Edelsbrunner, Herbert; Paterson, Michael S.
Publisher: University of Warwick. Department of Computer Science
Languages: English
Types: Other
Subjects: QA

Classified by OpenAIRE into

arxiv: Computer Science::Databases
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.
  • No references.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article