@inproceedings{8b7ec7350be94b759ebe0f229113b2be,

title = "On computing the centroid of the vertices of an arrangement and related problems",

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.",

author = "Deepak Ajwani and Saurabh Ray and Raimund Seidel and Tiwary, {Hans Raj}",

note = "Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 10th International Workshop on Algorithms and Data Structures, WADS 2007 ; Conference date: 15-08-2007 Through 17-08-2007",

year = "2007",

doi = "10.1007/978-3-540-73951-7_45",

language = "English (US)",

isbn = "3540739483",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "519--528",

booktitle = "Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings",

}