Browsing by Author "Kruse, David"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    ItemOpen Access
    Barrier resilience problems
    (2024) Kruse, David
    The barrier resilience problem can be stated as follows: Given two points s and t and a set of unit disks D in 2D-space, what is the minimum number of disks k that a curve connecting s and t must cross. It is currently unknown if there exists a polynomial time algorithm that can find the optimal solution k for any problem instance. This work aims to give an intuition on why it is difficult to solve and at the same time show some restrictions on the complexity, which prevent an easy reduction of NP-hard problems. As a result, neither a polynomial time algorithm nor a reduction of an NP-hard problem is currently known or discovered in this work. Existing ideas and approximations are explained and expanded upon, whilst also introducing novel algorithms. One technique used is linear programming, which was not previously considered for solving the barrier resilience problem. In contrast to previous works, the algorithms offer both upper and lower bounds for k, which are very useful in practice in restricting k to a small range of values, even restricting this range to only the optimal value k in most randomly generated instances. Existing and novel algorithms are implemented in C++. The different approximations are compared both theoretically and practically, with their performance in terms of runtime and accuracy being measured on random instances.