License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.42
URN: urn:nbn:de:0030-drops-104460
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10446/
van der Hoog, Ivor ;
Kostitsyna, Irina ;
Löffler, Maarten ;
Speckmann, Bettina
Preprocessing Ambiguous Imprecise Points
Abstract
Let R = {R_1, R_2, ..., R_n} be a set of regions and let X = {x_1, x_2, ..., x_n} be an (unknown) point set with x_i in R_i. Region R_i represents the uncertainty region of x_i. We consider the following question: how fast can we establish order if we are allowed to preprocess the regions in R? The preprocessing model of uncertainty uses two consecutive phases: a preprocessing phase which has access only to R followed by a reconstruction phase during which a desired structure on X is computed. Recent results in this model parametrize the reconstruction time by the ply of R, which is the maximum overlap between the regions in R. We introduce the ambiguity A(R) as a more fine-grained measure of the degree of overlap in R. We show how to preprocess a set of d-dimensional disks in O(n log n) time such that we can sort X (if d=1) and reconstruct a quadtree on X (if d >= 1 but constant) in O(A(R)) time. If A(R) is sub-linear, then reporting the result dominates the running time of the reconstruction phase. However, we can still return a suitable data structure representing the result in O(A(R)) time.
In one dimension, {R} is a set of intervals and the ambiguity is linked to interval entropy, which in turn relates to the well-studied problem of sorting under partial information. The number of comparisons necessary to find the linear order underlying a poset P is lower-bounded by the graph entropy of P. We show that if P is an interval order, then the ambiguity provides a constant-factor approximation of the graph entropy. This gives a lower bound of Omega(A(R)) in all dimensions for the reconstruction phase (sorting or any proximity structure), independent of any preprocessing; hence our result is tight. Finally, our results imply that one can approximate the entropy of interval graphs in O(n log n) time, improving the O(n^{2.5}) bound by Cardinal et al.
BibTeX - Entry
@InProceedings{vanderhoog_et_al:LIPIcs:2019:10446,
author = {Ivor van der Hoog and Irina Kostitsyna and Maarten L{\"o}ffler and Bettina Speckmann},
title = {{Preprocessing Ambiguous Imprecise Points}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {42:1--42:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10446},
URN = {urn:nbn:de:0030-drops-104460},
doi = {10.4230/LIPIcs.SoCG.2019.42},
annote = {Keywords: preprocessing, imprecise points, entropy, sorting, proximity structures}
}
|
Keywords: |
|
preprocessing, imprecise points, entropy, sorting, proximity structures |
|
Collection: |
|
35th International Symposium on Computational Geometry (SoCG 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
11.06.2019 |
