• DocumentCode
    761144
  • Title

    On computing connected components of line segments

  • Author

    Lopez, M.A. ; Thurimella, Ramakrishna

  • Author_Institution
    Dept. of Math. & Comput. Sci., Denver Univ., CO, USA
  • Volume
    44
  • Issue
    4
  • fYear
    1995
  • fDate
    4/1/1995 12:00:00 AM
  • Firstpage
    597
  • Lastpage
    601
  • Abstract
    It is shown that given a set of n line segments, their connected components can be computed in time O(n4/3log3n). A bound of o(n4/3) for this problem would imply a similar bound for detecting, for a given set of n points and n lines, whether some point lies on some of the lines. This problem, known as Hopcroft´s problem, is believed to have a lower bound of Ω(n4/3). For the special case when for each segment both endpoints fall inside the same face of the arrangement induced by the set of segments, we give an algorithm that runs in O(nlog3n) time
  • Keywords
    computational complexity; Hopcroft´s problem; connected components computing; line segments; lower bound; Circuits; Computational complexity; Computer science; Fabrication; Face detection; Mathematics; Space technology; Very large scale integration;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/12.376174
  • Filename
    376174