Three problems about dynamic convex hulls

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present three results related to dynamic convex hulls: A fully dynamic data structure for maintaining a set of n points in the plane so that we can find the edges of the convex hull intersecting a query line, with expected query and amortized update time O(log1+ε n) for an arbitrarily small constant ε > 0. This improves the previous bound of O(log3/2 n). A fully dynamic data structure for maintaining a set of n points in the plane to support halfplane range reporting queries in O(log n + k) time with O(polylog n) expected amortized update time. A similar result holds for 3-dimensional orthogonal range reporting. For 3- dimensional halfspace range reporting, the query time increases to O(log2 n/ log log n + k). A semi-online dynamic data structure for maintaining a set of n line segments in the plane, so that we can decide whether a query line segment lies completely above the lower envelope, with query time O(log n) and amortized update time O(nε). As a corollary, we can solve the following problem in O(n1+ε) time: given a triangulated terrain in 3-d of size n, identify all faces that are partially visible from a fixed viewpoint.

Original languageEnglish (US)
Title of host publicationProceedings of the 27th Annual Symposium on Computational Geometry, SCG'11
Pages27-36
Number of pages10
DOIs
StatePublished - 2011
Externally publishedYes
Event27th Annual ACM Symposium on Computational Geometry, SCG'11 - Paris, France
Duration: Jun 13 2011Jun 15 2011

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other27th Annual ACM Symposium on Computational Geometry, SCG'11
Country/TerritoryFrance
CityParis
Period6/13/116/15/11

Keywords

  • Convex hull
  • Dynamic data structures
  • Halfspace range searching
  • Lower envelopes
  • Orthogonal range searching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Three problems about dynamic convex hulls'. Together they form a unique fingerprint.

Cite this