Publication: Research › Ph.D. thesis

Geometric Cover is a large family of NP-complete special cases of the broader Set Cover problem.

Unlike the general problem, Geometric Cover involves objects that exist in a geometric setting,

consequently implying that they are all restricted to obeying some inherent structure. The

archetypal example is Line Cover, also known as Point-Line Cover, where a set of points in

a geometric space are to be covered by placing a restricted number of lines. We present new

FPT algorithms for the sub-family Curve Cover (which includes Line Cover), as well as for

Hyperplane Cover restricted to R 3 (i.e. Plane Cover), with improved time complexity compared

to the previous best results. Our improvements are derived from a more careful treatment of

the geometric properties of the covering objects than before, and invoking incidence bounds

from pure geometry.

An orientation of an un-directed graph is a directed version of it, i.e. where every un-directed

edge in the original graph has been replaced by a directed edge, incident on the same two vertices,

in either direction. Graph orientations with low out-degree are desirable as the foundation of

data structures with many applications. If the un-directed graph is dynamic (can be altered

by some outside actor), some orientations may need to be reversed in order to maintain the

low out-degree. We present a new algorithm that is simpler than earlier work, yet matches or

outperforms the efficiency of these results with very few exceptions.

Counter games are a type of abstract game played over a set of counters holding values,

and these values may be moved between counters according to some set of rules. Typically

they are played between two players: the adversary who tries to concentrate the greatest value

possible in a single counter, and the benevolent player who tries to prevent the adversary from

doing so. These counter games are sometimes used as a behind-the-scenes tool for proving the

efficiency of an algorithm, i.e. proving that the adversary is unable concentrate more than some

specific value in a counter, also proves that the algorithm cannot perform worse than this value.

We develop a new counter game with only one player (the adversary), and use it to prove the

efficiency of the graph orientation algorithm.

Unlike the general problem, Geometric Cover involves objects that exist in a geometric setting,

consequently implying that they are all restricted to obeying some inherent structure. The

archetypal example is Line Cover, also known as Point-Line Cover, where a set of points in

a geometric space are to be covered by placing a restricted number of lines. We present new

FPT algorithms for the sub-family Curve Cover (which includes Line Cover), as well as for

Hyperplane Cover restricted to R 3 (i.e. Plane Cover), with improved time complexity compared

to the previous best results. Our improvements are derived from a more careful treatment of

the geometric properties of the covering objects than before, and invoking incidence bounds

from pure geometry.

An orientation of an un-directed graph is a directed version of it, i.e. where every un-directed

edge in the original graph has been replaced by a directed edge, incident on the same two vertices,

in either direction. Graph orientations with low out-degree are desirable as the foundation of

data structures with many applications. If the un-directed graph is dynamic (can be altered

by some outside actor), some orientations may need to be reversed in order to maintain the

low out-degree. We present a new algorithm that is simpler than earlier work, yet matches or

outperforms the efficiency of these results with very few exceptions.

Counter games are a type of abstract game played over a set of counters holding values,

and these values may be moved between counters according to some set of rules. Typically

they are played between two players: the adversary who tries to concentrate the greatest value

possible in a single counter, and the benevolent player who tries to prevent the adversary from

doing so. These counter games are sometimes used as a behind-the-scenes tool for proving the

efficiency of an algorithm, i.e. proving that the adversary is unable concentrate more than some

specific value in a counter, also proves that the algorithm cannot perform worse than this value.

We develop a new counter game with only one player (the adversary), and use it to prove the

efficiency of the graph orientation algorithm.

Original language | English |
---|

Number of pages | 81 |
---|---|

State | Submitted - 13 Sep 2017 |

See relations at Aarhus University Citationformats

ID: 117024138