In class we proved that the 1D line segment intersection problem has an inherent difficulty of Ω(n log n). Briefly expla
Posted: Mon Jun 06, 2022 5:38 pm
In class we proved that the 1D line segment intersection problem
has an inherent difficulty of
Ω(n log n). Briefly explain why the 2D line
segment intersection problem also required Ω(n log
n)
time.
Note: For 1D line segment we can use Element
Uniqueness to establish a lower bound on the
1D Line Segment Intersection problem.This simple reduction also
holds for the 2D Line Segment
Intersection. since 1D problem is hard which has an inherent
difficulty of Ω(n log n) is a special
case of 2D problems where all y coordinates are zero
has an inherent difficulty of
Ω(n log n). Briefly explain why the 2D line
segment intersection problem also required Ω(n log
n)
time.
Note: For 1D line segment we can use Element
Uniqueness to establish a lower bound on the
1D Line Segment Intersection problem.This simple reduction also
holds for the 2D Line Segment
Intersection. since 1D problem is hard which has an inherent
difficulty of Ω(n log n) is a special
case of 2D problems where all y coordinates are zero