Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

1987 | Buch

Fundamental Concepts in Combinatorial Geometry Kapitel lesen Erstes Kapitel lesen

Algorithms in Combinatorial Geometry

verfasst von: Prof. Dr. Herbert Edelsbrunner

Verlag: Springer Berlin Heidelberg

Buchreihe : Monographs in Theoretical Computer Science. An EATCS Series

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Computational geometry as an area of research in its own right emerged in the early seventies of this century. Right from the beginning, it was obvious that strong connections of various kinds exist to questions studied in the considerably older field of combinatorial geometry. For example, the combinatorial structure of a geometric problem usually decides which algorithmic method solves the problem most efficiently. Furthermore, the analysis of an algorithm often requires a great deal of combinatorial knowledge. As it turns out, however, the connection between the two research areas commonly referred to as computa­ tional geometry and combinatorial geometry is not as lop-sided as it appears. Indeed, the interest in computational issues in geometry gives a new and con­ structive direction to the combinatorial study of geometry. It is the intention of this book to demonstrate that computational and com­ binatorial investigations in geometry are doomed to profit from each other. To reach this goal, I designed this book to consist of three parts, acorn binatorial part, a computational part, and one that presents applications of the results of the first two parts. The choice of the topics covered in this book was guided by my attempt to describe the most fundamental algorithms in computational geometry that have an interesting combinatorial structure. In this early stage geometric transforms played an important role as they reveal connections between seemingly unrelated problems and thus help to structure the field.

Inhaltsverzeichnis

Frontmatter

Combinatorial Geometry

Frontmatter
Chapter 1. Fundamental Concepts in Combinatorial Geometry
Abstract
Two of the main subjects studied in combinatorial geometry and therefore in this book are finite sets of points and finite sets of hyperplanes. Not all questions about finite sets of points or hyperplanes are combinatorial, though, and one has to keep in mind that a strict classification into combinatorial and non-combinatorial problems is neither reasonable nor desirable. Nevertheless, there are a few characteristics that identify a problem as combinatorial. For example, a typical combinatorial question that can be asked about a set P of n points in d-dimensional Euclidean space E d is the following:
  • “How many partitions of P into two subsets can be defined by hyperplanes?”
  • If H is a set of n hyperplanes in the same space, then it is a combinatorial question if one asks
  • “What is the number of cells the space is cut into by the hyperplanes in H?”
  • We will investigate both problems and many related ones in this chapter and, more generally, in this book.
Herbert Edelsbrunner
Chapter 2. Permutation Tables
Abstract
It is sometimes easier to analyze arrangements and, equivalently, configurations by encoding them into a combinatorial structure that is easy to manipulate. Among the combinatorial structures that were proposed for combinatorial investigations of arrangements and configurations, so-called circular sequences belong to the most elegant and most useful ones. They can be used to represent two-dimensional arrangements of lines and configurations of points in the plane.
Herbert Edelsbrunner
Chapter 3. Semispaces of Configurations
Abstract
A non-vertical hyperplane h, disjoint from a finite set P of points, partitions P into two sets P+ = P∩h+ and P- = P∩h - called semispaces of P, where h+ is the open half-space above hyperplane h and h- is the open half-space below h. Note that this definition includes the empty set and P itself as semispaces of P. Using geometric transformations and the face counting formulas for arrangements of hyper planes presented in Chapter 1, it is not hard to find tight upper bounds on the number of semispaces of P that depend solely on the cardinality of P. Unfortunately, little is known about the maximum number of semispaces with some fixed cardinality. This chapter addresses the latter counting problem and derives non-trivial upper and lower bounds.
Herbert Edelsbrunner
Chapter 4. Dissections of Point Sets
Abstract
A hyperplane that contains no point of a finite set P partitions P into two subsets contained in the two half-spaces defined by the hyperplane. Equivalently, a point contained in a cell of an arrangement A(H) classifies each hyperplane h in H according to whether it is above or below h. Examples of two related combinatorial problems that are interesting to ask are
Is there a point p which is such that the partition of P defined by any hyper-plane that contains p is reasonably balanced? and If P is a set of points in E d , are there d hyperplanes that partition P into 2 d subsets of approximately the same size?
Herbert Edelsbrunner
Chapter 5. Zones in Arrangements
Abstract
In this chapter, we investigate the complexity of the boundary of a certain collection of cells in an arrangement of hyperplanes. We formalize the problem by introducing the notion of a so-called zone which is defined relative to some chosen hyperplane in the arrangement. Intuitively, the zone of a hyperplane h contains all faces in the boundaries of those cells which are supported by h. The introduction of this concept is motivated by an algorithm that constructs an arrangement incrementally, that is, the hyperplanes are inserted one after another (see Chapter 7). A more formal definition of the zone of a hyper plane in terms of visibility is as follows.
Herbert Edelsbrunner
Chapter 6. The Complexity of Families of Cells
Abstract
It will become apparent in Chapters 7 through 15 of this book that many computational problems in geometry can be solved by constructing arrangements of hyperplanes. Unfortunately, the rather large number of faces of arrangements entails the use of large amounts of storage. It is thus advantageous to construct only part of an arrangement whenever the problem at hand admits it. Examples of useful structures in arrangements are single cells or faces (see Chapter 8), zones (see Chapters 5 and 7), stabbing regions (see Chapter 15), and levels (see Chapters 3, 9, and 13).
Herbert Edelsbrunner

Fundamental Geometric Algorithms

Frontmatter
Chapter 7. Constructing Arrangements
Abstract
This chapter investigates the problem of constructing an arrangement of hyper-planes, that is, of creating a structure which represents all faces and all incidences between faces of the arrangement. While it might be true that this problem is interesting in its own right, the applications of an algorithm for this problem, demonstrated in Chapters 12 and 13, make it one of the most fundamental problems in computational geometry. An algorithm that constructs an arrangement A(H) can be used to answer many questions about the set H of hyper planes, about the dual configuration D(H), and about other related concepts.
Herbert Edelsbrunner
Chapter 8. Constructing Convex Hulls
Abstract
This chapter investigates the problem of constructing the convex hull of a finite set of points in E d , that is, of producing a meaningful representation of the convex hull. If P is a finite set of points in E d , then we write convP for the convex hull of P. By the definitions given in Appendix A, convP is the set of convex combinations of P. Equivalently, convP can be defined as
the smallest convex set that contains P, or the intersection of all convex sets that contain P, or the intersection of all half-spaces that contain P.
Herbert Edelsbrunner
Chapter 9. Skeletons in Arrangements
Abstract
We have seen in Chapters 7 and 8 that there are optimal algorithms known for constructing a complete arrangement of hyperplanes (Chapter 7) and for constructing a single cell in an arrangement provided the number of dimensions is even or equal to three (Chapter 8). Less satisfying methods are available if a structure in an arrangement is to be computed that is more complicated than a single cell. There are two obvious strategies for such computations, which are not without disadvantages, however.
Herbert Edelsbrunner
Chapter 10. Linear Programming
Abstract
Solving linear programs is one of the best investigated and most important problems in mathematical optimization. Formally, it is the problem of minimizing a linear objective function
$$ {{\upsilon }_{1}}{{x}_{1}} + {{\upsilon }_{2}}{{x}_{2}} + \cdots + {{\upsilon }_{d}}{{x}_{d}} $$
subject to a collection of constraints, where each constraint is a linear inequality
$$ {{\omega }_{{i,1}}}{{x}_{1}} + {{\omega }_{{i,2}}}{{x}_{2}} + ... + {{\omega }_{i}}{{,}_{d}}{{x}_{d}} \leqslant {{\omega }_{{i,d + 1,}}}$$
for real numbers υ1 through υd and ω i,1 through ωi ,d+1,. If the linear program involves d variables, x1,x2,...,xd, then each inequality can be interpreted as a closed half-space in E d , and the collection of constraints becomes a convex polyhedron Pthat is the intersection of all half-spaces. The problem is then to find a point x =(ξ1,ξ2,..., ξd) in P if it exists, that minimizes
$$ \left\langle {u,x} \right\rangle = {{\upsilon }_{1}}{{\xi }_{1}} + {{\upsilon }_{2}}{{\xi }_{2}} + \cdots + {{\upsilon }_{d}}{{\xi }_{d}}, $$
where u =(v 1,v2,...,v d ). is the vector which defines the objective function. Intuitively, x; is a point of P which lies furthest in the direction determined by the vector −u = (−v1, −v2,..., −v d ). However, such a point does not always exist. We will return to this issue in Section 10.1, where we discuss the different types of linear programs existing and where we specify what we require from a solution to a linear program.
Herbert Edelsbrunner
Chapter 11. Planar point Location Search
Abstract
One of the more fundamental problems in computational geometry is that of locating a specific point in a given two-dimensional subdivision. It is thus necessary to define a subdivision appropriately. An embedding ∈ of a graph g maps each node v of g to a point ∈(v) in E 2 and each arc a = {v,w} to a simple connected curve ∈(a) with endpoints ∈(v) and ∈(w). The embedding ∈ is plane if ∈(v)≠∈(w), for any two nodes v≠w of g, and if ∈(a)∩∈(b)=Ø, for any two arcs a≠b of g so we assume that a curve ∈(a) does not contain its endpoints. Graph g is planar if it admits a plane embedding of itself. The embedding of a node of g is called a vertex, the embedding of an arc is called an edge, and a connected component of E2 reduced by all vertices and edges is called a region. For the sake of generality, we admit one node of g to be embedded at infinity; thus, all incident arcs correspond to unbounded edges of the subdivision, and all unbounded edges of the subdivision correspond to arcs incident upon this node. The embedding of a node at infinity is called an improper vertex. In formal terms, the point location search problem can now be defined as follows:
let S be a subdivision of E 2; for a given query point q, determine which of the regions, edges, and vertices of S contains point q.
Herbert Edelsbrunner

Geometric and Algorithmic Applications

Frontmatter
Chapter 12. Problems For Configurations and Arrangements
Abstract
A more appropriate but longer title for this chapter would be “Problems formulated for configurations and solved for arrangements”1. In fact, many problems formulated for configurations, whether combinatorial or algorithmic, are easier to approach in dual space where an arrangement of hyperplanes represents the configuration. It is safe to say that the translation of the problem into dual space makes it easier to see some aspects of the problem which are otherwise hidden; these aspects may or may not be important for a solution.
Herbert Edelsbrunner
Chapter 13. Voronoi Diagrams
Abstract
A Voronoi diagram is a cell complex which is defined with respect to a finite set of objects in some Euclidean space. Each cell of the diagram belongs to one object of the set and contains all points for which this object is the closest, or the one with the dominant influence in some sense. The Voronoi diagram in fact expresses the proximity information of the set of objects at hand in a very explicit and computationally useful manner. We will see examples of uses of this information (in particular in Section 13.2). First, we provide a rather general definition of the notion of a Voronoi diagram which subsumes all common variants as specializations.
Herbert Edelsbrunner
Chapter 14. Separation and Intersection in the Plane
Abstract
This chapter presents applications of the combinatorial results in Part I and the computational results in Part II to separation and intersection problems in Euclidean spaces. A typical problem in this category, which will not be discussed in this chapter, however, is the linear separability of two point sets in E d . This is the question whether or not there is a hyperplane such that two given point sets are contained in different closed half-spaces defined by the hyperplane. This problem has been briefly discussed in Chapter 10, and we have seen that there is an algorithm which finds a separating hyperplane in time linear in the total number of points, if it exists.
Herbert Edelsbrunner
Chapter 15. Paradigmatic Design of Algorithms
Abstract
The design of efficient algorithms is an art which is closely related to the art of proving theorems. In both disciplines, there are a few methods that work in relatively many cases and which are therefore worth becoming standard tools in the repertoire of every active designer. This chapter reviews and discusses some of the methods, called design paradigms, that have found repeated application in Chapters 7 through 14. We include the initial mathematical investigation of a given problem in this discussion, and we exclude the use of standard general purpose programs, like sorting, searching in graphs, etc. This does not imply, however, that we do not believe these general purpose programs to be among the most important tools that a designer of algorithms can have to his or her disposal.
Herbert Edelsbrunner
Backmatter
Metadaten
Titel
Algorithms in Combinatorial Geometry
verfasst von
Prof. Dr. Herbert Edelsbrunner
Copyright-Jahr
1987
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-61568-9
Print ISBN
978-3-642-64873-1
DOI
https://doi.org/10.1007/978-3-642-61568-9