On Finding Ordinary or Monochromatic Intersection Points

Details On Finding Ordinary or Monochromatic Intersection Points On Finding Ordinary or Monochromatic Intersection Points

2009-10-01

arxiv.org/abs/0910.0286v1

Computer Science

Computational Geometry

21 pages, 4 figures

Scientific paper

An algorithm is demonstrated that finds an ordinary intersection in an arrangement of $n$ lines in $\mathbb{R}^2$, not all parallel and not all passing through a common point, in time $O(n \log{n})$. The algorithm is then extended to find an ordinary intersection among an arrangement of hyperplanes in $\mathbb{R}^d$, no $d$ passing through a line and not all passing through the same point, again, in time $O(n \log{n})$. Two additional algorithms are provided that find an ordinary or monochromatic intersection, respectively, in an arrangement of pseudolines in time $O(n^2)$.

Affiliated with

Also associated with

No associations

Rating

On Finding Ordinary or Monochromatic Intersection Points does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Finding Ordinary or Monochromatic Intersection Points, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Finding Ordinary or Monochromatic Intersection Points will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-25691