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

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

doi:10.1007/978-3-540-73951-7_45

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

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 log² n) algorithm for computing this centroid. For arrangements of n segments we give an O(n^4/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 log⁵ n) time bound. Our bounds also generalize to certain natural weighted versions of those problems.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings
Publisher	Springer Verlag
Pages	519-528
Number of pages	10
ISBN (Print)	3540739483, 9783540739487
DOIs	https://doi.org/10.1007/978-3-540-73951-7_45
State	Published - 2007
Event	10th International Workshop on Algorithms and Data Structures, WADS 2007 - Halifax, Canada Duration: Aug 15 2007 → Aug 17 2007

Publication series

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

Other

Other	10th International Workshop on Algorithms and Data Structures, WADS 2007
Country/Territory	Canada
City	Halifax
Period	8/15/07 → 8/17/07

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-73951-7_45

Cite this

Ajwani, D., Ray, S., Seidel, R., & Tiwary, H. R. (2007). On computing the centroid of the vertices of an arrangement and related problems. In Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings (pp. 519-528). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4619 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-73951-7_45

On computing the centroid of the vertices of an arrangement and related problems. / Ajwani, Deepak; Ray, Saurabh; Seidel, Raimund et al.
Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Springer Verlag, 2007. p. 519-528 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4619 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ajwani, D, Ray, S, Seidel, R & Tiwary, HR 2007, On computing the centroid of the vertices of an arrangement and related problems. in Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4619 LNCS, Springer Verlag, pp. 519-528, 10th International Workshop on Algorithms and Data Structures, WADS 2007, Halifax, Canada, 8/15/07. https://doi.org/10.1007/978-3-540-73951-7_45

Ajwani D, Ray S, Seidel R, Tiwary HR. On computing the centroid of the vertices of an arrangement and related problems. In Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Springer Verlag. 2007. p. 519-528. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-73951-7_45

Ajwani, Deepak ; Ray, Saurabh ; Seidel, Raimund et al. / On computing the centroid of the vertices of an arrangement and related problems. Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Springer Verlag, 2007. pp. 519-528 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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}",

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

}

TY - GEN

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

AU - Ajwani, Deepak

AU - Ray, Saurabh

AU - Seidel, Raimund

AU - Tiwary, Hans Raj

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=38149055778&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38149055778&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-73951-7_45

DO - 10.1007/978-3-540-73951-7_45

M3 - Conference contribution

AN - SCOPUS:38149055778

SN - 3540739483

SN - 9783540739487

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 519

EP - 528

BT - Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings

PB - Springer Verlag

T2 - 10th International Workshop on Algorithms and Data Structures, WADS 2007

Y2 - 15 August 2007 through 17 August 2007

ER -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this