Online Routing in Convex Subdivisions (2002)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
Online Routing in Convex Subdivisions (2002)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
A General Approach to Dominance in the Plane (2001)
Svante Carlsson, I. Vakgroep Informatica, Svante Carlsson T, Mark H. Overmars
Given two points p and q and a set of points 0 in the plane, p is said to dominate q with respect to O if p dominates q and there is no o O such that p dominates o and o dominates q. In other words,...
Worst Case Constant Time Priority Queue (2000)
Andrej Brodnik, Svante Carlsson, Johan Karlsson, J. Ian Munro
We present a new data structure of size 3M +o(M) bits for solving
Resizable Arrays in Optimal Time and Space (2000)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, Robert Sedgewick
. We present simple, practical and efficient data structures for the fundamental problem of maintaining a resizable one-dimensional array, A[l::l + n Gamma 1], of fixed-size elements, as elements are...
Online Routing in Convex Subdivisions (2000)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
Construction of a Tree from its Traversals in Optimal Time and Space (1999)
Arne Andersson, Svante Carlsson
Given the preorder traversal of a tree together with some additional structure information, the tree can be constructed in linear time with a simple algorithm. The additional information may be the...
Finding the Shortest Watchman Route in a Simple Polygon (1998)
Svante Carlsson, Hkan Jonsson, Bengt J. Nilsson
We present the ørst polynomial-time algorithm that ønds the shortest route in a simple polygon such that all points of the polygon are visible from the route. This route is called the shortest...
Sub-linear Decoding of Huffman Codes Almost In-Place (1998)
Andrej Brodnik, Svante Carlsson
We present a succinct data structure storing the Huffman encoding that permits sublinear decoding in the number of transmitted bits. The size of the extra storage except for the storage of the...
Sub-linear Decoding of Huffman Codes Almost In-Place (1998)
Andrej Brodnik, Svante Carlsson
We present a succinct data structure storing the Huffman encoding that permits sublinear decoding in the number of transmitted bits. The size of the extra storage except for the storage of the...
Approximating the Shortest Watchman Route in a Simple Polygon (1997)
Svante Carlsson, Hkan Jonsson, Bengt J. Nilsson
We present a fast algorithm for computing a watchman route in a simple polygon that is at most a constant factor longer than the shortest watchman route. The algorithm runs in O(n log n) time as...
Computing Vision Points in Polygons (1997)
Svante Carlsson, Bengt J. Nilsson
We consider a restricted version of the art gallery problem within simple polygons in which the guards are required to lie on a given one-dimensional object, a watchman route. We call this problem...
Small Forwarding Tables for Fast Routing Lookups (1997)
Andrej Brodnik, Svante Carlsson
For some time, the networking community has assumed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry...
Optimum Guard Covers and m-Watchmen Routes for Restricted Polygons (1996)
Svante Carlsson, Bengt J. Nilsson, Simeon Ntafos
A watchman, in the terminology of art galleries, is a mobile guard. We consider several watchman and guard problems for different classes of polygons. We introduce the notion of vision spans along a...
A Fast Expected-Time Compacting Garbage-Collection Algorithm (Position Paper) (1993)
Svante Carlsson, Christer Mattsson
We introduce a new compacting garbage-collection algorithm with a very good averagecase performance. The algorithm combines the advantages of the two most frequently used algorithms for this purpose,...
Small Forwarding Tables for Fast Routing Lookups (1970)
Andrej Brodnik, Svante Carlsson
For some time, the networking community has assumed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry...
Small Forwarding Tables for Fast Routing Lookups (1970)
Andrej Brodnik, Svante Carlsson
For some time, the networking community has assumed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry...
Online Routing in Convex Subdivisions (1970)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Pat Morin, J. Ian Munro
. We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...