We present efficient data structures for approximate nearest neighbor searching and approximate 2-point shortest path queries in a two-dimensional polygonal domain P with n vertices. Our goal is to store a dynamic set of m point sites S in P so that we can efficiently find a site s ∈ S closest to an arbitrary query point q. We will allow both insertions and deletions in the set of sites S. However, as even just computing the distance between an arbitrary pair of points q, s ∈ P requires a substantial amount of space, we allow for approximating the distances. Given a parameter ε > 0, we build an O(ⁿ /_ε log n) space data structure that can compute a 1 + εapproximation of the distance between q and s in O(_ε^1/₂ log n) time. Building on this, we then obtain an O(^n+m/ε log n + ^m/_ε log m) space data structure that allows us to report a site s ∈ S so that the distance between query point q and s is at most (1 + ε)-times the distance between q and its true nearest neighbor in O(_ε^1/₂ log n + ¹ /_ε log n log m + ¹ /_ε log² m) time. Our data structure supports updates in O(_ε^1/₂ log n + ^1/_ε log n log m + ¹ /_ε log² m) amortized time. ... Read more

Programmable networks enable us to define the behaviour of a network through software. This added freedom comes with added complexity because multiple switches need to coordinate and be programmed correctly. To ease this task, we focus on intent-based networking via program synthesis. In this paper, we explain how to leverage linear temporal logic to describe the desired behaviour of a program, how to verify a P4 program against that description, and how to use the formula describing the program's behaviour to reduce the search space of the program synthesiser. ... Read more