The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
This article is a survey on research done in recent years at FU Berlin applying methods from Computational Geometry to problems in pattern and shape analysis. In particular, algorithms are described for determining the exact and approximate congruence of finite sets of points in the plane. This problem is generalized to polygonal curves in the plane, where variuos cases are considered depending on...
Geographic database systems, known as geographic information systems (GISs) particularly among non-computer scientists, are one of the most important applications of the very active research area named spatial database systems. Consequently following the database approach, a GIS has to be seamless, i.e. store the complete area of interest (e.g. the whole world) in one database map. For exhibiting...
The management of spatial data in applications such as graphics and image processing, geography as well as computer aided design (CAD) imposes stringent new requirements on socalled spatial database systems. In this paper we propose a flexible and extensible index manager for efficient query processing in spatial database systems by integrating spatial access methods. An essential ingredient for efficient...
The management of spatial data in applications such as graphics and image processing, geography as well as computer aided design (CAD) imposes stringent new requirements on spatial database systems, in particular on efficient query processing of complex spatial objects. In this paper, we propose a two-level, multi-representation query processing technique which consists of a filter and a refinement...
Breadth-first ray tracing for realistic image synthesis differs from usual pixel-by-pixel rendering in tracing whole generations of rays together. This means that first all rays of view are treated, next the set of reflection and refraction rays, then the reflection and refraction rays caused by them, and so on. The calculation of intersections for a generation of rays uses the ray-z-buffer algorithm...
In this paper we survey some results in restricted orientation computational geometry. The aim is to embed our own results into a more general context. We discuss methods for making object queries, computing shortest paths, and questions on restricted orientation convexity. Furthermore, we give an optimal algorithm for computing shortest paths when three arbitrary orientations are allowed for path...
We are concerned with the problem of partitioning complex scenes of geometric objects in order to support the solutions of proximity problems in general metric spaces with an efficiently computable distance function. We present a data structure called Monotonous Bisector Tree, which can be regarded as a divisive hierarchical approach of centralized clustering methods (compare [3] and [12]). We analyze...
In order to learn a convex set C, an algorithm is given a random sample of points and the information which of the points belong to C. From this sample a set C′ is constructed which is supposed to be a good approximation of C. The algorithm may have a small probability of failing. We measure the quality of the approximation by minimizing the probability that a random test point selected under the...
This paper surveys basic concepts of spatial access structures for geometric databases. We discuss the isolated plausibility arguments on which spatial access structure design decisions are traditionally based whenever efficiency is the primary goal, and we propose a more integrated view. This helps to explain phenomena that have been observed in experiments, and it lays the foundation for tailoring...
Every set S of n points in the plane has a spanning tree such that no line disjoint from S has more than O(√n) intersections with the tree (where the edges are embedded as straight line segments). We review the proof of this result (originally proved by Bernard Chazelle and the author in a more general setting), point at some methods for constructing such a tree, and describe some algorithmic and...
We describe and analyze a new high performance universal class of hash functions which can be constructed fast, evaluated in constant time, and which have properties very similar to the “ideal” hash function, namely a random function. We illustrate the capabilities of the new class by considering simple perfect hashing schemes. We further survey recent results in a very important application...
We present our distributed αΒ-algorithm and show how αΒ- enhancements like iterative deepening, transposition tables, history tables etc. that are useful in the sequential game tree search can be applied to a distributed algorithm. The methods we describe are suitable even for large distributed systems. We describe an extension of the Young Brothers Wait Concept that we introduced to reduce the search...
This paper analyzes three methods for packet routing on grids. The central algorithmic concept is to achieve a good performance by keeping the processor load balanced. At first, packets are considered as atomic. A balanced load is guaranteed by the algorithm itself. By using techniques like orthogonal overlapping of simple algorithms and colouring highly efficient, but complicated algorithms can be...
Determining time necessary for computing important functions on parallel machines is one of the most important problems in complexity theory for parallel algorithms. Recently, a substantial progress has been made in this area. In this survey paper, we discuss the results that have been obtained for three types of parallel random access machines (PRAMs): CREW, ROBUST and EREW.
Two parallel, problem-specific algorithms to compute a certain optimization problem, the two-dimensional Bin Packing Problem, are set against. A parallel branch-&-bound procedure which guarantees to find the optimal solution is compard to a heuristic genetic algorithm which successively improves a set of solutions. Both algorithms were implemented on a local memory multiprocessor system of 32...
We consider the problem to construct reliable combinatorial and clocked circuits from unreliable basic elements. The main concern in this paper is the question how such fault-tolerance increases the circuit layout. In general it requires at least a logarithmic factor increase of the number of gates. We design area efficient codes for the information transfer within a Boolean circuit. Using such a...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.