19 citations · 44 across the 21 of their papers we have counts for
5 papers · 1 filter
Near-Optimal Algorithms for Point-Line Covering Problems
Jianer Chen, Qin Huang, Iyad Kanj +1
We study fundamental point-line covering problems in computational geometry, in which the input is a set of points in the plane. The first is the Rich Lines problem, which asks…
How to navigate through obstacles?
Eduard Eiben, Iyad Kanj
Given a set of obstacles and two points, is there a path between the two points that does not cross more than different obstacles? This is a fundamental problem that has underg…
Degree Four Plane Spanners: Simpler and Better
Iyad Kanj, Ljubomir Perković, Duru Türkoǧlu
Let be a set of points embedded in the plane, and let be the complete Euclidean graph whose point-set is . Each edge in between two p…
Finding Points in General Position
Vincent Froese, Iyad Kanj, André Nichterlein +1
We study computational aspects of the General Position Subset Selection problem defined as follows: Given a set of points in the plane, find a maximum-cardinality subset of points…
There are Plane Spanners of Maximum Degree 4
Nicolas Bonichon, Iyad Kanj, Ljubomir Perković +1
Let E be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G of E is said to be a t-spanner, or simply a spanner,…