1 Search Results for "Park, Eunhui"

Document

DOI: 10.4230/LIPIcs.SOCG.2015.781

Approximate Geometric MST Range Queries

Authors: Sunil Arya, David M. Mount, and Eunhui Park

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{arya_et_al:LIPIcs.SOCG.2015.781,
  author =	{Arya, Sunil and Mount, David M. and Park, Eunhui},
  title =	{{Approximate Geometric MST Range Queries}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{781--795},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.781},
  URN =		{urn:nbn:de:0030-drops-51233},
  doi =		{10.4230/LIPIcs.SOCG.2015.781},
  annote =	{Keywords: Geometric data structures, Minimum spanning trees, Range searching, Approximation algorithms}
}

Refine by Author
1 Arya, Sunil
1 Mount, David M.
1 Park, Eunhui

Refine by Classification

Refine by Keyword
1 Approximation algorithms
1 Geometric data structures
1 Minimum spanning trees
1 Range searching

Refine by Type
1 document

Refine by Publication Year
1 2015

1 Search Results for "Park, Eunhui"

Approximate Geometric MST Range Queries

Abstract

Cite as

Thanks for your feedback!

Could not send message