@string{LNCS = "Lecture Notes in Computer Science"} @Article{Aurenhammer:Voronoi, author = "Franz Aurenhammer", year = "1991", keywords = "COMPUTATIONAL-GEOMETRY VORONOI OVERVIEW SPATIAL CONVEX-HULL PROXIMITY", institution = "U.Graz, Austria", title = "Voronoi diagrams---a survey of a fundamental geometric data structure", journal = "ACM Computing Surveys, Sept 1991", volume = "23", number = "3", annote = "Explores many aspects of V.D.'s. No details of generalized models, but a list of other's work addressing generalized models. Details of the work by the Edelsbrunner group. ~ 150 references. - AM 10/91", } @InProceedings{Bartal:Probabilistic, title = "Probabilistic Approximations of Metric Spaces and its Algorithmic Applications", author = "Yair Bartal", pages = "184--193", booktitle = "37th Annual Symposium on Foundations of Computer Science {(FOCS'96)}", year = "1996", publisher = "IEEE", } @book{Bjorner:Oriented, author = "Anders Bj{\"o}rner and Las Vergnas, Michel and Bernd Sturmfels and Neil White and G{\"u}nter M. Ziegler", title = "Oriented Matroids", publisher = "Cambridge University Press", year = 1999, edition = "Second", } % " @InProceedings{Chavez:Proximity, title = "Proximity Searching in High Dimensional Spaces with a Proximity Preserving Order", author = "Edgar Ch{\'a}vez and Karina Figueroa and Gonzalo Navarro", pages = "405--414", booktitle = "4th Mexican International Conference on Artificial Intelligence {(MICAI'05)}", editor = "Alexander Gelbukh and {\'A}lvaro de Albornoz and Hugo Terashima-Mar{\'\i}n", publisher = "Springer", year = "2005", } @techreport{Chavez:Intrinsic, author = "Edgar Ch{\'a}vez and Gonzalo Navarro", title = "Measuring the Dimensionality of General Metric Spaces", institution = "Department of Computer Science, University of Chile", year = 2000, number = "TR/DCC-00-1", } @InProceedings{Figueroa:Least, title = "On the Least Cost for Proximity Searching in Metric Spaces", author = "Karina Figueroa and Edgar Ch{\'a}vez and Gonzalo Navarro and Rodrigo Paredes", pages = "279--290", booktitle = "Experimental and Efficient Algorithms: 5th International Workshop {(WEA'06)}", editor = "Carme {\`A}lvarez and Maria Serna", year = "2006", publisher = "Springer", } @manual{Figueroa:Metric, title = "Metric Spaces Library", author = "Karina Figueroa and Gonzalo Navarro and Edgar Ch{\'a}vez", note = "Online {\url{http://www.sisap.org/?f=library}.} Accessed November 24, 2007.", } @Book{Grunbaum:Arrangements, author = "Branko Gr{\"u}nbaum", title = "Arrangements and Spreads", publisher = "American Mathematical Society", year = "1971", number = "10", series = "Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics", address = "Providence", month = jun, ISBN = "0-8218-1659-4", } % " @InProceedings{Icking:Bisectors, author = "C. Icking and R. Klein and N.-M. L{\^e} and L. Ma and F. Santos", title = "On Bisectors for Convex Distance Functions in 3-Space", pages = "119--123", booktitle = "11th Canadian Conference on Computational Geometry ({CCCG}'99)", year = "1999", publisher = "University of British Columbia", } @Article{Icking:Convex, title = "Convex Distance Functions in 3-Space are Different", author = "Christian Icking and Rolf Klein and Ngoc-Minh L{\^e} and Lihong Ma", journal = "Fundamenta Informaticae", year = "1995", number = "4", volume = "22", bibdate = "2003-11-27", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/fuin/fuin22.html#IckingKLM95", pages = "331--352", } @Article{Lowe:Distinctive, author = "David G. Lowe", title = "Distinctive Image Features from Scale-Invariant Keypoints", journal = "International Journal of Computer Vision", volume = "60", year = "2004", number = "2", month = nov, pages = "91--110", URL = "http://dx.doi.org/10.1023/B:VISI.0000029664.99615.94", bibsource = "http://www.visionbib.com/bibliography/match588.html#TT39684", } @phdthesis{Mandel:Topology, author = "Arnaldo Mandel", title = "Topology of Oriented Matroids", school = "University of Waterloo", year = 1982, } @Article{Mico:New, title = "A new version of the nearest-neighbour approximating and eliminating search algorithm ({AESA}) with linear preprocessing time and memory requirements", author = "Luisa Mic{\'o} and Jos{\'e} Oncina and Enrique Vidal", journal = "Pattern Recognition Letters", year = "1994", number = "1", volume = "15", bibdate = "2005-01-18", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/prl/prl15.html#MicoOV94", pages = "9--17", URL = "http://dx.doi.org/10.1016/0167-8655(94)90095-7", } @InProceedings{Paredes:Using, title = "Using the {$k$}-Nearest Neighbor Graph for Proximity Searching in Metric Spaces", author = "Rodrigo Paredes and Edgar Ch{\'a}vez", pages = "127--138", booktitle = "String Processing and Information Retrieval, 12th International Conference {(SPIRE'05)}", editor = "Mariano P. Consens and Gonzalo Navarro", publisher = "Springer", year = "2005", } @article{Price:Some, author = "Derek J. Price", title = "Some unusual series occurring in $n$-dimensional geometry", journal = "The Mathematical Gazette", year = "1946", volume = 30, pages = "149--150", callno = "QA1.M7", } @phdthesis{Sahlgren:Word, title = "The Word-Space Model", author = "Magnus Sahlgren", school = "Stockholm University", year = "2006", note = "Online {\url{http://www.sics.se/~mange/TheWordSpaceModel.pdf}}.", } @Article{Santos:Delaunay, title = "On {Delaunay} Oriented Matroids for Convex Distance Functions", author = "Francisco Santos", journal = "Discrete \& Computational Geometry", year = "1996", number = "2", volume = "16", bibdate = "2002-12-02", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/dcg/dcg16.html#Santos96", pages = "197--210", URL = "http://link.springer.de/link/service/journals/00454/bibs/16n2p197.html", abstract = "For any finite point set S in E d , an oriented matroid DOM(S) can be defined in terms of how S is partitioned by Euclidean hyperspheres. This oriented matroid is related to the Delaunay triangulation of S and is realizable, because of the lifting property of Delaunay triangulations. We prove that the same construction of a Delaunay oriented matroid can be performed with respect to any smooth, strictly convex distance function in the plane E 2 (Theorem 3.5). For these distances, the existence of a Delaunay oriented matroid cannot follow from a lifting property, because Delaunay triangulations might be non-regular (Theorem 4.2(i). This is related to the fact that the Delaunay oriented matroid can be non-realizable (Theorem 4.2(ii) ). Keywords : oriented matroid, Delaunay triangulation, Voronoi diagram 1 Introduction In this paper we describe a link between the Delaunay triangulation of a finite point set S in the Euclidean d-space E d and a certain oriented matroid DOM(S) of ra...", } @InProceedings{Skala:Measuring, title = "Measuring the Difficulty of Distance-Based Indexing", author = "Matthew Skala", pages = "103--114", booktitle = "String Processing and Information Retrieval: 12th Internatio nal Conference {(SPIRE'05)}", editor = "Mariano P. Consens and Gonzalo Navarro", year = "2005", publisher = "Springer", } @article{Uhlmann:Satisfying, author = "Jeffrey K. Uhlmann", title = "Satisfying general proximity/similarity queries with metric trees", journal = "Information Processing Letters", year = 1991, volume = 40, pages = "175--179", month = nov # "~25,", } @Article{VidalRuiz:Algorithm, author = "E. Vidal Ruiz", title = "An Algorithm for Finding Nearest Neighbors in (Approximately) Constant Time", journal = "Pattern Recognition Letters", volume = "4", year = "1986", pages = "145--157", bibsource = "http://iris.usc.edu/Vision-Notes/bibliography/pattern621.html#TT40621", } @InProceedings{Yianilos:Data, author = "Peter N. Yianilos", title = "Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces", pages = "311--321", booktitle = "Fourth Annual {ACM/SIGACT-SIAM} Symposium on Discrete Algorithms {(SODA'93)}", year = "1993", publisher = "ACM/SIAM", }