MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Funke, Stefan
Malamatos, Theocharis
Matijevic, Domagoj
Wolpert, Nicola		dblp
dblp
dblp
dblp
Not MPG Author(s):
Malamatos, Theocharis
Matijevic, Domagoj
Editor(s):
Rappaport, Daviddblp
Not MPII Editor(s):
Rappaport, David
BibTeX cite key*:
FMMW2006
Title, Booktitle
Title*:
(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram
CCCG06paper.pdf (126.49 KB)
Booktitle*:
18th Canadian Conference on Computational Geometry
Event, URLs
Conference URL::
http://www.cs.queensu.ca/cccg/
Downloading URL:
http://www.cs.queensu.ca/cccg/papers/cccg7.pdf
Event Address*:
Kingston, Canada
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
14 August 2006
Event End Date:
16 August 2006
Publisher
Name*:
School of Computing, Queen's University
URL:
Address*:
Kingston, Ontario, K7L 3N6, Canada
Type:
Extended Abstract
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
23-26
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{FMMW2006,
AUTHOR = {Funke, Stefan and Malamatos, Theocharis and Matijevic, Domagoj and Wolpert, Nicola},
 EDITOR = {Rappaport, David},
 TITLE = {(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram},
 BOOKTITLE = {18th Canadian Conference on Computational Geometry},
 PUBLISHER = {School of Computing, Queen's University},
 YEAR = {2006},
 TYPE = {Extended Abstract},
 PAGES = {23--26},
 ADDRESS = {Kingston, Canada},
}

Entry last modified by Uwe Brahm, 04/23/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Domagoj Matijevic		Created
08/25/2006 08:12:48 PM
Revisions
2.
1.
0.

Editor(s)
Uwe Brahm
Stefan Funke
Domagoj Matijevic

Edit Dates
2007-04-23 10:31:38
02/22/2007 12:24:04 PM
08/25/2006 08:12:49 PM

File Attachment Icon
CCCG06paper.pdf