Reporting intersecting pairs of polytopes in two and three dimensions

Pankaj K. Agarwal, Mark de Berg, Sariel Har-Peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold

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

Abstract

Let P = {P1,…, Pm} be a set of m convex polytopes in Rd, for d = 2, 3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i, j) such that Piintersects Pj. For the planar case we describe a simple algorithm with running time O(n4/3log n + k), and an improved randomized algorithm with expected running time O((n logm + k)α(n) log n) (which is faster for small values of k). For d = 3, we present an O(n8/5+ε+ k)-time algorithm, for any ε > 0. Our algorithms can be modified to count the number of intersecting pairs in O(n4/3logO(1) n) time for the planar case, and in O(n8/5+ε) time and R3.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings
EditorsFrank Dehne, Jorg-Rudiger Sack, Roberto Tamassia
PublisherSpringer
Pages122-134
Number of pages13
ISBN (Print)3540424237, 9783540424239
DOIs
StatePublished - 2001
Event7th International Workshop on Algorithms and Data Structures, WADS 2001 - Providence, United States
Duration: Aug 8 2001Aug 10 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2125
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th International Workshop on Algorithms and Data Structures, WADS 2001
Country/TerritoryUnited States
CityProvidence
Period8/8/018/10/01

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Reporting intersecting pairs of polytopes in two and three dimensions'. Together they form a unique fingerprint.

Cite this