On computing the centroid of the vertices of an arrangement and related problems

Deepak Ajwani, Saurabh Ray, Raimund Seidel, Hans Raj Tiwary

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

Abstract

We consider the problem of computing the centroid of all the vertices in a non-degenerate arrangement of n lines. The trivial approach requires the enumeration of all (n/2) vertices. We present an O(n log2 n) algorithm for computing this centroid. For arrangements of n segments we give an O(n4/3+ε) algorithm for computing the centroid of its vertices. For the special case that all the segments of the arrangement are chords of a simply connected planar region we achieve an O(n log5 n) time bound. Our bounds also generalize to certain natural weighted versions of those problems.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings
PublisherSpringer Verlag
Pages519-528
Number of pages10
ISBN (Print)3540739483, 9783540739487
DOIs
StatePublished - 2007
Event10th International Workshop on Algorithms and Data Structures, WADS 2007 - Halifax, Canada
Duration: Aug 15 2007Aug 17 2007

Publication series

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

Other

Other10th International Workshop on Algorithms and Data Structures, WADS 2007
Country/TerritoryCanada
CityHalifax
Period8/15/078/17/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'On computing the centroid of the vertices of an arrangement and related problems'. Together they form a unique fingerprint.

Cite this