Bengt J. Nilsson

Prof. Dr. Bengt J. Nilsson

Department of Computer Science and Media Technology, Malmö University, 205 06 Malmö, Sweden

Research Focus & Metrics

Academic Career Length

28Years (1999-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
23 September 2019 in Algorithmica
Verified
Journal Article
Open access
PDF file
MCMarek Chrobak
Marek Chrobak
CDChristoph Dürr
Christoph Dürr
AFAleksander Fabijan
Aleksander Fabijan
BNBengt J. Nilsson
Bengt J. Nilsson
Clique clustering is the problem of partitioning the vertices of a graph into disjoint clusters, where each cluster forms a clique in the graph, while optimizing some objective function. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The goal is to maintain a clustering with an objective value close to the optimal solution. For the variant where we want to maximize the number of edges in the clusters, we propose an online algorithm based on the doubling technique. It has an asymptotic competitive ratio at most 15.646 and a strict competitive ratio at most 22.641. We also show that no deterministic algorithm can have an asymptotic competitive ratio better than 6. For the variant where we want to minimize the number of edges between clusters, we show that the deterministic competitive ratio of the problem is $$n-\omega (1)$$n-ω(1) , where n is the number of vertices in the graph.

19 June 2024 in Algorithmica
Verified
Journal Article
Open access
PDF file
BNBengt J. Nilsson
Bengt J. Nilsson
EPEli Packer
Eli Packer
The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times $$O(n^8)$$ O ( n 8 ) and $$O(n^4)$$ O ( n 4 ) respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in $$O(n^2)$$ O ( n 2 ) time, i.e., when two starting points of the two tours are given as input.

1 June 2020 in International Journal of Computational Geometry & Applications
Verified
Journal Article
Closed access
PDF file
BNBengt J. Nilsson
Bengt J. Nilsson
PŻPaweł Żyliński
Paweł Żyliński

25 March 1999
Verified
Conference Paper
Closed access
PDF file
TCTorgny E. Carlsson
Torgny E. Carlsson
JGJonny Gustafsson
Jonny Gustafsson
BNBengt J. Nilsson
Bengt J. Nilsson
In the development of new products there are two parallel lines for the development process to follow; the traditional or 'real,' and the new computer aided or 'virtual.' The traditional line is to develop prototypes that can be used for testing strength, functionality, and visual appearance of the product. In the virtual line digital (CAD) models are developed which can be tested entirely in a computer by simulations e.g., using Finite Element Analysis (FEA) and other tools. For transformation from the real to the virtual world some kind of 3D camera is needed. The shape of the model should be measured together with further data concerning the visual appearance, material properties, etc. We have developed electronic recording techniques for doing this based on the Light-in-Flight technique. This technology has all advantages of holography, i.e., apart from the shape it is also possible to measure how much light is reflected from different parts of the object along with interferometric information, which can give mechanical data for the object. This can be used for example for visualization and to give tactile and haptic information to a virtual reality system about how the object would be perceived by a person touching it.

11 January 2025 in Algorithmica
Verified
Journal Article
Open access
PDF file
OFOmrit Filtser
Omrit Filtser
EKErik Krohn
Erik Krohn
BNBengt J. Nilsson
Bengt J. Nilsson
CRChristian Rieck
Christian Rieck
CSChristiane Schmidt
Christiane Schmidt
We study the Art Gallery Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is -complete even in thin polyominoes (i.e., polyominoes that do not a contain a $$2\times 2$$ 2 × 2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a $$3\times 3$$ 3 × 3 block of cells) for all $$k\in {\mathbb {N}}$$ k ∈ N .

22 June 2024
Verified
Book Chapter
Closed access
PDF file
Andrej BrodnikAndrej Brodnik
Andrej Brodnik
BNBengt J. Nilsson
Bengt J. Nilsson
GVGordana Vujović
Gordana Vujović