Complexity of the union of (α, β)-covered objects

Research output: Contribution to conferencePaperpeer-review

20 Scopus citations

Abstract

An (α, β)-covered object is a simply connected planar region c with the property that for each point p∈∂c there exists a triangle contained in c and having p as a vertex, such that all its angles are at least α and all its edges are at least β·diam(c)-long. This notion extends that of fat convex objects. We show that the combinatorial complexity of the union of n (α, β)-covered objects of `constant description complexity' is O(λs+2(n) log2 n log log n), where s is the maximum number of intersections between the boundaries of any pair of the given objects.

Original languageEnglish (US)
Pages134-142
Number of pages9
DOIs
StatePublished - 1999
EventProceedings of the 1999 15th Annual Symposium on Computational Geometry - Miami Beach, FL, USA
Duration: Jun 13 1999Jun 16 1999

Other

OtherProceedings of the 1999 15th Annual Symposium on Computational Geometry
CityMiami Beach, FL, USA
Period6/13/996/16/99

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Complexity of the union of (α, β)-covered objects'. Together they form a unique fingerprint.

Cite this