| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427479 | Information Processing Letters | 2013 | 4 Pages |
•We study the problem searching a vertex with a desired property in the line arrangement.•We present efficient algorithms without using parametric search.•We apply our results to a points approximation problem and obtain an optimal solution without using parametric search.
We study the problem of searching for a vertex with a desired property in the arrangement of a set of lines in the plane. We show that this problem can be solved efficiently by modifying (and simplifying) two slope selection algorithms without using parametric search. We apply this result to a points approximation problem and obtain an optimal solution for it without using parametric search. Since this line arrangement searching problem is quite natural, our result may find other applications as well.
