The union of moving polygonal pseudodiscs : combinatorial bounds and applications

M. Berg, de, H. Everett, L.J. Guibas

    Research output: Contribution to journalArticleAcademicpeer-review

    10 Citations (Scopus)

    Abstract

    Let P be a set of polygonal pseudodiscs in the plane with n edges in total translating with fixed velocities in fixed directions. We prove that the maximum number of combinatorial changes in the union of the pseudodiscs in P is T(n2a(n)). In general, if the pseudodiscs move along curved trajectories, then the maximum number of changes in the union is T(n¿s+2(n)), where s is the maximum number of times any triple of polygon edges meet in a common point. We apply this result to prove that the complexity of the space of lines missing a set of n convex homothetic polytopes of constant complexity in 3-space is O(n2¿4(n)). This bound is almost tight in the worst case.
    Original languageEnglish
    Pages (from-to)69-81
    Number of pages13
    JournalComputational Geometry
    Volume11
    Issue number2
    DOIs
    Publication statusPublished - 1998

    Fingerprint Dive into the research topics of 'The union of moving polygonal pseudodiscs : combinatorial bounds and applications'. Together they form a unique fingerprint.

    Cite this