RUC. Repositorio da Universidade da Coruña
Publication
Artículo científico (JournalArticle)
The largest empty circle with location constraints in spatial databases
[Abstract]: Given a set S of points in the two-dimensional space, which are stored in a spatial database, this paper presents an efficient algorithm to find, in the area delimited by those points, the empty circle with the largest area that contains only a query point q. Our algorithm adapts previous work in the field of computational geometry to be used in spatial databases, which requires to manage large amounts of data. To achieve this objective, the basic idea is to discard a large part of the points of S, in such a way that the problem can be solved providing only the remaining points to a classical computational geometry algorithm that, by processing a smaller collection of points, saves main memory resources and computation time. The correctness of our algorithm is formally proven. In addition, we empirically show its efficiency and scalability by running a set of experiments using both synthetic and real data., For the first author, this work was supported by the research projects DIUBB [140515 3/R;
142719 3/R]s and MECESUP [UBB0704]. For the rest of authors by Ministerio de Economía
y Competitividad (PGE and FEDER) under grants [TIN2016-78011-C4-1-R, TIN2013-46238-
C4-3-R] and Centro para el desarrollo Tecnol´ogico e Industrial under grants [IDI-20141259,
ITC-20151305, ITC-20151247]. The authors also want to thank Boaz Ben Moshe for sharing
his Java Delaunay code and for kindly answering our questions., University of Bío-Bío; 140515 3/R, University of Bío-Bío; 142719 3/R, Chile. Ministerio de Educación; UBB0704
Project:
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 TIN2016-78011-C4-1-R
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 TIN2013-46238-C4-3-R
,
MINECO / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 IDI-20141259
,
MINECO / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 ITC-20151305
,
MINECO / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 ITC-20151247
HANDLE: http://hdl.handle.net/2183/40139
View at: http://hdl.handle.net/2183/40139