Improved bounds for the union complexity of fat objects

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

Abstract

We introduce a new class of fat, not necessarily convex or polygonal, objects in the plane, namely locally ¿-fat objects. We prove that the union complexity of any set of n such objects is O(¿ s¿+¿2(n)log2 n). This improves the best known bound, and extends it to a more general class of objects.
Original languageEnglish
Title of host publicationFSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science (Proceedings 25th International Conference, Hyderabad, India, December 15-18, 2005)
EditorsR. Ramanujam, S. Sen
Place of PublicationBerlin
PublisherSpringer
Pages116-127
ISBN (Print)3-540-30495-9
DOIs
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
Volume3821
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Improved bounds for the union complexity of fat objects'. Together they form a unique fingerprint.

Cite this