English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  (Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram

Funke, S., Malamatos, T., Matijevic, D., & Wolpert, N. (2006). (Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram. In 18th Canadian Conference on Computational Geometry (pp. 23-26). Kingston, Ontario, K7L 3N6, Canada: School of Computing, Queen's University.

Item is

Files

show Files
hide Files
:
CCCG06paper.pdf (Any fulltext), 127KB
 
File Permalink:
-
Name:
CCCG06paper.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Funke, Stefan1, Author           
Malamatos, Theocharis1, Author           
Matijevic, Domagoj1, Author           
Wolpert, Nicola1, Author           
Rappaport, David, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: For a given point set in Euclidean space we consider the problem of finding (approximate) nearest neighbors of a query point but restricting only to points that lie within a fixed cone with apex at the query point. Apart from being a rather natural question to ask, solutions to this problem have applications in surface reconstruction and dimension detection. We investigate the structure of the Voronoi diagram induced by this notion of proximity and present approximate and exact data structures for answering cone-restricted nearest neighbor queries. In particular we develop an approximate Voronoi diagram of size $O((n/\epsilon^d)\log (1/\epsilon))$ that can be used to answer cone-restricted nearest neighbor queries in $O(\log (n/\epsilon))$ time.

Details

show
hide
Language(s): eng - English
 Dates: 2007-04-232006
 Publication Status: Issued
 Pages: -
 Publishing info: Kingston, Ontario, K7L 3N6, Canada : School of Computing, Queen's University
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314361
Other: Local-ID: C1256428004B93B8-07FA7E47F576294BC12571D500640CD3-FMMW2006
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Kingston, Canada
Start-/End Date: 2006-08-14

Legal Case

show

Project information

show

Source 1

show
hide
Title: 18th Canadian Conference on Computational Geometry
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Kingston, Ontario, K7L 3N6, Canada : School of Computing, Queen's University
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 23 - 26 Identifier: -