Reporting All Segment Intersections Using an Arbitrary Sized Work Space

Matsuo KONAGAYA; Tetsuo ASANO

doi:10.1587/transfun.E96.A.1066

Reporting All Segment Intersections Using an Arbitrary Sized Work Space

Matsuo KONAGAYA, Tetsuo ASANO

Full Text Views

0

Share
Cite this

Summary :

This paper presents an efficient algorithm for reporting all intersections among n given segments in the plane using work space of arbitrarily given size. More exactly, given a parameter s which is between Ω(1) and O(n) specifying the size of work space, the algorithm reports all the segment intersections in roughly O(n²/+ K) time using O(s) words of O(log n) bits, where K is the total number of intersecting pairs. The time complexity can be improved to O((n²/s) log s + K) when input segments have only some number of different slopes.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.6 pp.1066-1071

Publication Date: 2013/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E96.A.1066

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Matsuo KONAGAYA, Tetsuo ASANO, "Reporting All Segment Intersections Using an Arbitrary Sized Work Space" in IEICE TRANSACTIONS on Fundamentals, vol. E96-A, no. 6, pp. 1066-1071, June 2013, doi: 10.1587/transfun.E96.A.1066.
Abstract: This paper presents an efficient algorithm for reporting all intersections among n given segments in the plane using work space of arbitrarily given size. More exactly, given a parameter s which is between Ω(1) and O(n) specifying the size of work space, the algorithm reports all the segment intersections in roughly O(n²/+ K) time using O(s) words of O(log n) bits, where K is the total number of intersecting pairs. The time complexity can be improved to O((n²/s) log s + K) when input segments have only some number of different slopes.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.1066/_p

Copy

@ARTICLE{e96-a_6_1066,
author={Matsuo KONAGAYA, Tetsuo ASANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Reporting All Segment Intersections Using an Arbitrary Sized Work Space},
year={2013},
volume={E96-A},
number={6},
pages={1066-1071},
abstract={This paper presents an efficient algorithm for reporting all intersections among n given segments in the plane using work space of arbitrarily given size. More exactly, given a parameter s which is between Ω(1) and O(n) specifying the size of work space, the algorithm reports all the segment intersections in roughly O(n²/+ K) time using O(s) words of O(log n) bits, where K is the total number of intersecting pairs. The time complexity can be improved to O((n²/s) log s + K) when input segments have only some number of different slopes.},
keywords={},
doi={10.1587/transfun.E96.A.1066},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - Reporting All Segment Intersections Using an Arbitrary Sized Work Space
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1066
EP - 1071
AU - Matsuo KONAGAYA
AU - Tetsuo ASANO
PY - 2013
DO - 10.1587/transfun.E96.A.1066
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2013
AB - This paper presents an efficient algorithm for reporting all intersections among n given segments in the plane using work space of arbitrarily given size. More exactly, given a parameter s which is between Ω(1) and O(n) specifying the size of work space, the algorithm reports all the segment intersections in roughly O(n²/+ K) time using O(s) words of O(log n) bits, where K is the total number of intersecting pairs. The time complexity can be improved to O((n²/s) log s + K) when input segments have only some number of different slopes.
ER -