## 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} ϵ R
_{i}. Region Ri 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 (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.

Original language | English |
---|---|

Title of host publication | 35th International Symposium on Computational Geometry (SoCG 2019) |

Editors | Gill Barequet, Yusu Wang |

Place of Publication | Dagstuhl, Germany |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Pages | 42:1-42:16 |

Number of pages | 16 |

Volume | 129 |

ISBN (Electronic) | 9783959771047 |

ISBN (Print) | 978-3-95977-104-7 |

DOIs | |

Publication status | Published - 1 Jun 2019 |

Event | 35th International Symposium on Computational Geometry, (SoCG2019) - Portland, United States Duration: 18 Jun 2019 → 21 Jun 2019 http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=80745©ownerid=35838 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 129 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 35th International Symposium on Computational Geometry, (SoCG2019) |
---|---|

Abbreviated title | SoCG2019 |

Country/Territory | United States |

City | Portland |

Period | 18/06/19 → 21/06/19 |

Internet address |

## Keywords

- And phrases preprocessing
- Entropy
- Imprecise points
- Proximity structures
- Sorting