On a class of O(n²) problems in computational geometry

There are many problems in computational geometry for which the best know algorithms take time @Q(n^2) (or more) in the worst case while only very low lower bounds are known. In this paper we describe a large class of problems for which we prove that ...

Many works related to dually chordal graphs, their cliques and neighborhoods were published by Brandstadt et al. (1998) [1] and Gutierrez (1996) [6]. We will undertake a similar study by considering minimal vertex separators and their properties ...

We are interested in the problem of covering simple orthogonal polygons with the minimum number of r-stars; an orthogonal polygon is an r-star if it is star-shaped. The problem has been considered by Worman and Keil [13] who described an algorithm ...