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)$$ , where n is the number of vertices in the graph.
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)$$ and $$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)$$ 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
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.
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$$ 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$$ block of cells) for all $$k\in {\mathbb {N}}$$ .