Optimization and approximation on systems of geometric by van Leeuwen E.

By van Leeuwen E.

Show description

Read or Download Optimization and approximation on systems of geometric objects PDF

Similar geometry and topology books

Plane Geometry and its Groups

San Francisco 1967 Holden-Day. octavo. , 288pp. , index, hardcover. superb in VG DJ, a couple of small closed tears.

Additional info for Optimization and approximation on systems of geometric objects

Sample text

Chapter 4 Geometric Intersection Graphs and Their Representation As is clear from the previous chapter, a fundamental problem for most classes of geometric intersection graphs is how to recognize such graphs. The recognition problem is often NP-hard and in PSPACE, but membership of NP is not always known. One way of proving membership of NP is to find a representation of the graph that uses polynomially many bits (polynomial in the number of vertices of the graph). This is a polynomial representation.

An object s is said to be scaled around a point p by τ > 0 if (assuming s is the only object in the space) s is translated by −p, the space is scaled by τ , and then s is translated by p. Scaling an object around a point gives more control over the scaling, which is needed in the following definition. 2 An object s is scalable if there is a point p ∈ int(s) such that for any τ ∈ R>0 \{1}, scaling s around p by τ gives an object s for which cl(s) ⊆ int(s ) or cl(s ) ⊆ int(s). If s is scalable, fix such a point p and call it the scaling point of s, denoted by cs .

Not every graph is a string graph) [241, 242, 98]. A relatively recent overview of the results in this area and a description of further classes can be found in the course notes of Kratochv´ıl [175]. 2 Intersection Graphs of Higher Dimensional Objects Another way to generalize interval graphs, more in line with further topics of this thesis, is to consider d-dimensional objects that are intervals if d = 1. A good example are intersection graphs of d-dimensional axis-parallel boxes. g. [a1 , b1 ] × · · · × [ad , bd ] for numbers ai < bi .

Download PDF sample

Rated 4.04 of 5 – based on 16 votes