Document Open Access Logo

Approximate Geometric MST Range Queries

Authors Sunil Arya, David M. Mount, Eunhui Park

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.781.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Sunil Arya
David M. Mount
Eunhui Park

Cite As Get BibTex

Sunil Arya, David M. Mount, and Eunhui Park. Approximate Geometric MST Range Queries. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 781-795, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.781

Abstract

Range searching is a widely-used method in computational geometry for efficiently accessing local regions of a large data set. Typically, range searching involves either counting or reporting the points lying within a given query region, but it is often desirable to compute statistics that better describe the structure of the point set lying within the region, not just the count.

In this paper we consider the geometric minimum spanning tree (MST) problem in the context of range searching where approximation is allowed. We are given a set P of n points in R^d. The objective is to preprocess P so that given an admissible query region Q, it is possible to efficiently approximate the weight of the minimum spanning tree of the subset of P lying within Q. There are two natural sources of approximation error, first by treating Q as a fuzzy object and second by approximating the MST weight itself. To model this, we assume that we are given two positive real approximation parameters eps_q and eps_w. Following the typical practice in approximate range searching, the range is expressed as two shapes Q^- and Q^+, where Q^- is contained in Q which is contained in Q^+, and their boundaries are separated by a distance of at least eps_q diam(Q). Points within Q^- must be included and points external to Q^+ cannot be included. A weight W is a valid answer to the query if there exist subsets P' and P'' of P, such that Q^- is contained in P' which is contained in P'' which is contained in Q^+ and wt(MST(P')) <= W <= (1+eps_w) wt(MST(P'')).

In this paper, we present an efficient data structure for answering such queries. Our approach uses simple data structures based on quadtrees, and it can be applied whenever Q^- and Q^+ are compact sets of constant combinatorial complexity. It uses space O(n), and it answers queries in time O(log n + 1/(eps_q eps_w)^{d + O(1)}). The O(1) term is a small constant independent of dimension, and the hidden constant factor in the overall running time depends on d, but not on eps_q or eps_w. Preprocessing requires knowledge of eps_w, but not eps_q.

Subject Classification

Keywords
  • Geometric data structures
  • Minimum spanning trees
  • Range searching
  • Approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. K. Agarwal, L. Arge, S. Govindarajan, J. Yanga, and K. Yi. Efficient external memory structures for range-aggregate queries. Comput. Geom. Theory Appl., 46:358-370, 2013. Google Scholar
  2. A. Andoni, A. Nikolov, K. Onak, and G. Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proc. 46th Annu. ACM Sympos. Theory Comput., pages 574-583, 2014. Google Scholar
  3. S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. Assoc. Comput. Mach., 45:753-782, 1998. Google Scholar
  4. S. Arya and T. M. Chan. Better ε-dependencies for offline approximate nearest neighbor search, euclidean minimum spanning trees, and ε-kernels. In Proc. 30th Annu. Sympos. Comput. Geom., pages 416-425, 2014. Google Scholar
  5. S. Arya and D. M. Mount. Approximate range searching. Comput. Geom. Theory Appl., 17:135-163, 2000. Google Scholar
  6. S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching. J. Assoc. Comput. Mach., 45:891-923, 1998. Google Scholar
  7. M. J. Bannister, W. E. Devanny, M. T. Goodrich, J. A. Simons, and L. Trott. Windows into geometric events: Data structures for time-windowed querying of temporal point sets. In Proc. 26th Canad. Conf. Comput. Geom., 2014. Google Scholar
  8. M. J. Bannister, C. DuBois, D. Eppstein, and P. Smyth. Windows into relational events: data structures for contiguous subsequences of edges. In Proc. 24th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 856-864, 2013. (arXiv:1209.5791). Google Scholar
  9. P. Brass, C. Knauer, C.-S. Shin, M. Smid, and I. Vigan. Range-aggregate queries for geometric extent problems. In Proc. 19th Computing: The Australasian Theory Symposium (CATS), pages 3-10, 2013. Google Scholar
  10. P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. Assoc. Comput. Mach., 42:67-90, 1995. Google Scholar
  11. P. B. Callahan and S. R. Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In Proc. Eighth Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 291-300, 1997. Google Scholar
  12. A. Czumaj, F. Ergün, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, and C. Sohler. Approximating the weight of the Euclidean minimum spanning tree in sublinear time. SIAM J. Comput., 35:91-109, 2005. Google Scholar
  13. A. Czumaj and C. Sohler. Estimating the weight of metric minimum spanning trees in sublinear time. SIAM J. Comput., 39:904-922, 2009. Google Scholar
  14. G. Frahling, P. Indyk, and C. Sohler. Sampling in dynamic data streams and applications. Internat. J. Comput. Geom. Appl., 18:3-28, 2008. Google Scholar
  15. Y. Nekrich and M. Smid. Approximating range-aggregate queries using coresets. In Proc. 22nd Canad. Conf. Comput. Geom., pages 253-256, 2010. Google Scholar
  16. D. Papadias, Y. Tao, K. Mouratidis, and K. Hui. Aggregate nearest neighbor queries in spatial databases. ACM Transactions on Database Systems (TODS), 30:529-576, 2005. Google Scholar
  17. E. Park and D. M. Mount. Output-sensitive well-separated pair decompositions for dynamic point sets. In Proc. 21st Internat. Conf. on Advances in Geographic Information Systems, pages 364-373, 2013. (doi: 10.1145/2525314.2525364). Google Scholar
  18. J. Shan, D. Zhang, and B. Salzberg. On spatial-range closest-pair query. In T. Hadzilacos, Y. Manolopoulos, J. Roddick, and Y. Theodoridis, editors, Advances in Spatial and Temporal Databases, volume 2750 of Lecture Notes in Computer Science, pages 252-269. Springer, Berlin, 2003. Google Scholar
  19. Y. Tao and D. Papadias. Range aggregate processing in spatial databases. IEEE Transactions on Knowledge and Data Engineering (TKDE), 16:1555-1570, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact