ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Articles  (117)
  • Computational geometry  (117)
  • Springer  (117)
  • Oxford University Press
  • Computer Science  (117)
  • 1
    Electronic Resource
    Electronic Resource
    Rational parameterization of quadrics and their offsets (1996)
    Springer
    Computing 57 (1996), S. 135-147 
    Details
    ISSN: 1436-5057
    Keywords: 68U05 (14J26) ; Computational geometry ; triangular and quadrangular patches ; rational Bézier patches ; rational offsets ; quadrics ; rational parameterization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Die Arbeit studiert zwei mit Quadriken in Zusammenhang stehenden Probleme. Einerseits werden quadratische Bézier Dreiecke auf Quadriken gekennzeichnet. Andererseits wird gezeigt, daß die Parallelflächen regulärer Flächen zweiter Ordnung stets rational sind, und es werden Algorithmen zur Berechnung der rationalen Parametrisierung angegeben.
    Notes: Abstract In this paper, we study two problems related to quadrics. One is the representation of triangular and quadrangular patches on quadrics: a necessary and sufficient condition is given for triangular patches on quadrics to be representable as rational quadratic triangular Bézier surfaces. The other is the rationality of the offsets to quadrics: the offsets of regular quadrics are shown to be rational and the algorithms are given for computing their rational parameterizations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02276876
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Algorithm for constrained delaunay triangulation (1994)
    Springer
    The visual computer 10 (1994), S. 255-265 
    Details
    ISSN: 1432-2315
    Keywords: Delaunay triangulation ; Computational geometry ; Constrained triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A direct algorithm for computing constrained Delaunay triangulation in 2-D is presented. The algorithm inserts points along the constrained edges (break lines) to maintain the Delaunay criterion. Since many different insertions are possible, the algorithm computes only those that are on the Delaunay circles of each intersected triangle. A shelling procedure is applied to put triangles together in such a way that completeness and correctness are guaranteed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901582
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Algorithms for computing the center of area of a convex polygon (1994)
    Springer
    The visual computer 10 (1994), S. 432-442 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Center ; Partition ; Symmetry measure ; Winternitz
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The center of area of a convex polygonP is the unique pointp * that maximizes the minimum area overlap betweenP and any halfplane that includesp *. We show thatp * is unique and present two algorithms for its computation. The first is a combinatorial algorithm that runs in timeO (n 6 log2 n). The second is a “numerical” algorithm that runs in timeO(GK(n+K)) whereK represents the number of desired bits of precision in the output coordinates andG the number of bits used to represent the coordinates of the input polygon vertices. We conclude with a discussion of implementation issues and related results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01910633
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    An algorithm for recognizing palm polygons (1994)
    Springer
    The visual computer 10 (1994), S. 443-451 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Palm polygon ; Weak visibility polygon ; Visibility graph ; Kernel
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A polygonP is said to be apalm polygon if there exists a pointx∈P such that the Euclidean shortest path fromx to any pointy∈P makes only left turns or only right turns. The set of all such pointsx is called thepalm kernel. In this paper we propose an O(E) time algorithm for recognizing a palm polygonP, whereE is the size of the visibility graph ofP. The algorithm recognizes the given polygonP as a palm polygon by computing the palm kernel ofP. If the palm kernel is not empty,P is a palm polygon.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01910634
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Optimal algorithms for symmetry detection in two and three dimensions (1985)
    Springer
    The visual computer 1 (1985), S. 37-48 
    Details
    ISSN: 1432-2315
    Keywords: Symmetry ; Similarity ; Computational geometry ; Pattern matching ; Graph isomorphism
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Exact algorithms for detecting all rotational and involutional symmetries in point sets, polygons and polyhedra are described. The time complexities of the algorithms are shown to be θ (n) for polygons and θ (n logn) for two- and three-dimensional point sets. θ (n logn) time is also required for general polyhedra, but for polyhedra with connected, planar surface graphs θ (n) time can be achieved. All algorithms are optimal in time complexity, within constants.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901268
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Hidden-surface removal in polyhedral cross-sections (1988)
    Springer
    The visual computer 3 (1988), S. 329-343 
    Details
    ISSN: 1432-2315
    Keywords: Hidden-surface problems ; Computational geometry ; Priority orderings ; Decomposition techniques ; Dynamization techniques
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Many of the fundamental problems in computer graphics involve the notion of visibility. In one approach to the hiddensurface problem, priorities are assigned to the faces of a scene. A realistic image is then rendered by displaying the faces with the resulting priority ordering. We introduce a tree-based formalism for describing priority orderings that simplifies an existing algorithm. As well, a decompositionbased algorithm is presented for classes of scenes that do not in general admit priority orderings. The algorithm requiresO(n logn) time ift=1 andO(tn logn+n logn logm) time ift〉1, wheren andm are respectively the number of faces and polyhedra in the scene, andt is a minimum decomposition factor of the scene. Finally, the tree-based formalism is used in the development ofO(n) time insertion and deletion algorithms that solve the problem of dynamically maintaining a priority ordering.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901191
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Visibility problems for orthogonal objects in two-or three-dimensions (1988)
    Springer
    The visual computer 4 (1988), S. 84-97 
    Details
    ISSN: 1432-2315
    Keywords: Visibility ; Hidden-line elimination ; Orthogonal objects ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract LetP be a set ofl points in 3-space, and letF be a set ofm opaque rectangular faces in 3-space with sides parallel tox- ory-axis. We present anO(n logn) time andO(n) space algorithm for determining all points inP which are visible from a viewpoint at (0,0,∞), wheren=l+m. We also present anO(n logn+k) time andO(n) space algorithm for the hidden-line elimination problem for the orthogonal polyhedra together with a viewpoint at (0,0,∞), wheren is the number of vertices of the polyhedra andk is the number of edge intersections in the projection plane.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01905560
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Applications of the 4×4 determinant method and the POLYGON ENGINE (1988)
    Springer
    The visual computer 4 (1988), S. 176-187 
    Details
    ISSN: 1432-2315
    Keywords: Interference problems ; Geometric modelling ; Computational geometry ; Solid modelling ; Hidden line and surface detections ; Geometry engine
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In the first half of the paper, various types of processing pertaining to a polygon, using the 4×4 determinant theories are explained along with a new containment test algorithm of a point in a polygon. In the latter half of the paper, a general-purpose geometric processor, the POLYGON ENGINE, is presented which can deal with various types of interference problems, such as Boolean operations in solid modelling, hidden line and surface eliminations, ray tracing and so on. It is, a successor of the TRIANGLE PROCESSOR and is also based upon the 4×4 determinant theories [4–6]. While the TRIANGLE PROCESSOR processes a triangulated polygon on a triangle-by-triangle basis, the POLYGON ENGINE can treat a polygon without triangulation. The latter is expected to be more functional, more efficient and easier to use.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01887590
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Recognizing polygons, or how to spy (1988)
    Springer
    The visual computer 3 (1988), S. 344-355 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Geometric algorithms ; Complexity ; Polygon recognition ; Star-shapedness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A new class of so-called pseudo-starshaped polygons is introduced. A polygon is pseudo-star-shaped if there exists a point from which the whole interior of the polygon can be seen, provided it is possible to see through single edges. We show that the class of pseudo-star-shaped polygons unifies and generalizes the well-known classes of convex, monotone and pseudostar-sphaped polygons. We give algorithms for testing whether a polygon is pseudostar-shaped from a given point in linear time, and for constructing all regions from which the polygon is pseudo-star-shaped in quadratic time. We show the latter algorithm to be worst-case optimal. Also, we give efficient algorithms solving standard geometrical problems such as point-location and triangulation for pseudo-starshaped polygons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901192
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    A simple linear algorithm for intersecting convex polygons (1985)
    Springer
    The visual computer 1 (1985), S. 118-123 
    Details
    ISSN: 1432-2315
    Keywords: Algorithms ; Complexity ; Computational geometry ; Convex polygons ; Intersection
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract LetP andQ be two convex polygons withm andn vertices, respectively, which are specified by their cartesian coordinates in order. A simpleO(m+n) algorithm is presented for computing the intersection ofP andQ. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01898355
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    An efficient algorithm for identifying objects using robot probes (1994)
    Springer
    The visual computer 10 (1994), S. 452-458 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Algorithm ; Robot probe ; Identifying ; Robot finger
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract When robot finger probes are used to recognize objects,m-1 probes are necessary and sufficient to identify an object with a fixed orientation and position among a set ofm convex planarn-sided objects. An algorithm is presented to preprocess a set of objects for efficient probing, together with a probing scheme and algorithms to delete objects from or to insert objects into the set.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01910635
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    Clustering methods for geometric objects and applications to design problems (1986)
    Springer
    The visual computer 2 (1986), S. 31-38 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Clustering ; Layout problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Clustering of geometric objects is a very familiar and important problem in many different areas of applications as well as in the theoretical foundation of some modern fields of computer science. This paper describes how design problems, especially the design of an assembly line, can be transformed into a clustering problem. In order to solve the problem for large sizes of input data we introduce a structure, called Voronoi Tree, which applied to our real world data (assembly line design) did not only reduce the time to get a feasible design of an assembly line dramatically, but additionally increased the value of the design by more than 30% (in comparison with standard design methods). In addition to this we introduce a clustering method which is of interest for those applications which can be transformed to planar clustering problems. In this particular case it is possible to compute an (hierarchically) optimized clustering with resp. to a large class of clustering measures in timeO(nn1/2log3 n+U F(n)nn1/2+P F(n)) [n: number of points;U F(n), PF(n) dependent on the chosen clustering measure].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01890985
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    An application of algebraic topology to solid modeling in molecular biology (1987)
    Springer
    The visual computer 3 (1987), S. 72-81 
    Details
    ISSN: 1432-2315
    Keywords: Solid modeling ; Algebraic topology ; Computational geometry ; Molecular graphics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A recurring problem in solid modeling, computer graphics, and molecular modeling is the computation of the intersection of two objects. A general solution to this problem is obtained by applying two ideas of algebraic topology: (1) a chain complex, and (2) a boundary formula for the intersection of two objects. A general data structure for a chain complex made up of piecewise polynomial cells is described, as are algorithms for connectivity, containment and intersection. The basic ideas of this work are abstract, topological, and for the most part, independent of the shape and dimensionality of the objects. An application to structural molecular biology is presented. The application identifies convex and concave features of protein surfaces.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02153663
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    An efficient algorithm for line and polygon clipping (1991)
    Springer
    The visual computer 7 (1991), S. 19-28 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Polygon algorithms ; Polygon elipping ; Line clipping ; Simulation of simplicity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We present an algorithm for clipping a polygon or a line against a convex polygonal window. The algorithm demonstrates the practicality of various ideas from computational geometry. It spendsO(logp) time on each edge of the clipped polygon, wherep is the number of window edges, while the Sutherland-Hodgman algorithm spendsO(p) time per edge. Theoretical and experimental analyses show that the constants involved are small enough to make the algorithm competitive even for windows with four edges. The algorithm enables image-space clipping against windows whose boundaries are convex spline curves. The paper contains detailed pseudo-code implementation of the algorithm and an adaptation of the simulation of simplicity method for handling degenerate cases.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01994114
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    A geometry-based investigation of the tool path generation for zigzag pocket machining (1991)
    Springer
    The visual computer 7 (1991), S. 296-308 
    Details
    ISSN: 1432-2315
    Keywords: Pocket machining ; Tool path generation ; Scanline method ; Computational geometry ; Geometric reasoning
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We present a detailed description of a zigzag algorithm for pocket machining. The algorithm is capable of computing correct zigzag tool paths for multiply-connected planar areas (“pockets”) bounded by a wide class of curves. It features a number of optimizations with respect to geometrical and technological objectives. In particular, a near-optimum inclination of the tool path is automatically determined. The underlying geometric principles are simple enough to allow the algorithm to be included in a numerical control computer.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01905694
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    Efficient triangulation of simple polygons (1991)
    Springer
    The visual computer 7 (1991), S. 280-295 
    Details
    ISSN: 1432-2315
    Keywords: Polygon ; Algorithm ; Triangulation ; Computational geometry ; Geometric Complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper considers the topic of efficiently traingulating a simple polygon with emphasis on practical and easy-to-implement algorithms. It also describes a newadaptive algorithm for triangulating a simplen-sided polygon. The algorithm runs in timeO(n(1+t o)) witht 0〈n. The quantityt 0 measures theshape-complexity of thetriangulation delivered by the algorithm. More preciselyt 0 is the number of obtained triangles contained in the triangulation that share zero edges with the input polygon and is, furthermore, related to the shape-complexity of theinput polygon. Although the worst-case complexity of the algorithm isO(n 2), for several classes of polygons it runs in linear time. The practical advantages of the algorithm are that it is simple and does not require sorting or the use of balanced tree structures. On the theoretical side, it is of interest because it is the first polygon triangulation algorithm where thecomputational complexity is a function of theoutput complexity. As a side benefit, we introduce a new measure of the complexity of a polygon triangulation that should find application in other contexts as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01905693
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    The Superman problem (1994)
    Springer
    The visual computer 10 (1994), S. 459-473 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Visibility ; Trapezoidization ; Circlecover minimization ; Lower bound
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Given a polygonK contained in a polygonP, and a points lying outsideP, we present a Θ (n logn) algorithm that finds the minimum number of edges, ofP that we want to retain in order to hidek froms. Furthermore, if the visibility polygon ofs givenK is unbounded, the algorithm is shown to run in linear time. This paper is dedicated to J. Siegel and J. Shuster.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01910636
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    Translation separability of sets of polygons (1987)
    Springer
    The visual computer 3 (1987), S. 227-235 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Data structures ; Motion problems ; Separability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider the problem of separating a set of polygons by a sequence of translations (one such collision-free translation motion for each polygon). If all translations are performed in a common direction the separability problem so obtained has been referred to as the uni-directional separability problem; for different translation directions, the more general multi-directional separability problem arises. The class of such separability problems has been studied previously and arises e.g. in computer graphics and robotics. Existing solutions to the uni-directional problem typically assume the objects to have a certain predetermined shape (e.g., rectangular or convex objects), or to have a direction of separation already available. Here we show how to compute all directions of unidirectional separability for sets of arbitrary simple polygons. The problem of determining whether a set of polygons is multi-directionally separable had been posed by G.T. Toussaint. Here we present an algorithm for solving this problem which, in addition to detecting whether or not the given set is multidirectionally separable, also provides an ordering in which to separate the polygons. In case that the entire set is not multi-directionally separable, the algorithm will find the largest separable subset.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01952829
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    Solving visibility and separability problems on a mesh-of-processors (1988)
    Springer
    The visual computer 3 (1988), S. 356-370 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Mesh-of-Processors ; Parallel algorithms ; Separability-Visibility
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms: - AnO( $$\sqrt N$$ time algorithm for computing on a Mesh-of-Processors of size N the visibility polygon from a point located in anN-vertex polygon, possibly with holes. -O( $$\sqrt N$$ ) time algorithms for computing on a Mesh-of-Processors of sizeN the set of all points on the boundary of anN-vertex polygonP which are visible in a given directiond as well as the visibility hull ofP for a given directiond. - AnO( $$\sqrt N$$ ) time algorithm for detecting on a Mesh-of-Processors of size 2N whether twoN-vertex polygons are separable in a given direction and anO( $$\sqrt {MN}$$ ) time algorithm for detecting on a Mesh-of-Processors of sizeMN whetherM N-vertex polygons are sequentially separable in a given direction. All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901193
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    An adaptive, error-free computation based on the 4×4 determinant method (1993)
    Springer
    The visual computer 9 (1993), S. 173-181 
    Details
    ISSN: 1432-2315
    Keywords: 4×4 determinant method ; Computational geometry ; Geometric modeling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The 4×4 determinant method makes it possible to unify geometric processing by the computations of 4×4 determinants composed of homogeneous coordinants vectors of four points or coefficient vectors of four plane equations. Because the method needs not require a division operation, error-free geometric computation is not difficult to realize by means of integer arithemtic of appropriate data length. The present paper proposes an error-free, efficient computing method, which computes the 4×4 determinants by adaptively selecting integer arithmetic of variable data length. This technique is discussed theoretically and experimentally.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901722
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    Electronic Resource
    Electronic Resource
    Voronoi diagrams with barriers and on polyhedra for minimal path planning (1985)
    Springer
    The visual computer 1 (1985), S. 133-150 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Robotics ; Minimal paths ; Voronoi diagrams ; Planar partitions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Two generalizations of the Voronoi diagram in two dimensions (E2) are presented in this paper. The first allows impenetrable barriers that the shortest path must go around. The barriers are straight line segments that may be combined into polygons and even mazes. Each region of the diagram delimits a set of points that have not only the same closest existing point, but have the same topology of shortest path. The edges of this diagram, which has linear complexity in the number of input points and barrier lines, may be hyperbolic sections as well as straight lines. The second construction considers the Voronoi diagram on the surface of a convex polyhedron, given a set of fixed source points on it. Each face is partitioned into regions, such that the shortest path to any goal point in a given region from the closest fixed source point travels over the same sequence of faces to the same closest point.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01898357
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    Detection of rotational and involutional symmetries and congruity of polyhedra (1996)
    Springer
    The visual computer 12 (1996), S. 193-201 
    Details
    ISSN: 1432-2315
    Keywords: Key words: Symmetry detection ; Congruity problem ; Algorithm design ; Graph theory ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: O (m 2) time and uses O(m) space, where m is the number of edges of the polyhedron. As this is the lower bound of the symmetry detection problem for the considered output form, our algorithm is optimal. We show that a slight modification of our symmetry detection algorithm can be used to solve the related conguity problem of polyhedra.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01782322
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    Optical clustering (1986)
    Springer
    The visual computer 2 (1986), S. 39-43 
    Details
    ISSN: 1432-2315
    Keywords: Clustering methods ; Computational geometry ; Picture analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper presents a definition of ‘optical clusters’ which is derived from the concept of optical resolution. The clustering problem (induced by this definition) is transformed such that the application of well known Computational Geometry methods yields efficient solutions. One result (which can be extended to different classes of objects and metrices) is the following: Given a setS ofN disjoint line segments inE 2. (a) The optical clusters with respect to a given separation parameterr∈R can be computed in timeO(Nlog2 N). (b) Given an interval [a, b] for the numberm(S, r) of optical clusters which we want to compute, then timeO(N log2 N)[O(Nlog2 N+CN)] suffices to compute the interval [R(b),R(a)]={r∈R/m(S,r)∈[a,b]} [allC optical clusterings withR(b)≦ r≦R(a)].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01890986
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    Theoretical foundations for the 4×4 determinant method in computer graphics and geometric modelling (1987)
    Springer
    The visual computer 3 (1987), S. 88-97 
    Details
    ISSN: 1432-2315
    Keywords: Interference problems ; Geometric modelling ; Computational geometry ; Solid modelling ; Hidden line ; Surface detections
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Theories of the 4×4 determinant method to resolve interference problems are described, in detail, in succession to the former paper [1]. First, various cases of the 4×4 determinant are discussed including the geometric implications by deriving a few fundamental relations. Secondly, normalization of the determinant is proposed. Thirdly, an intersection formula in homogeneous coordinates is verified which makes it possible to do consistent homogenous coordinate processing from the very beginning of geometric modelling to the very last of the objects displayed. Lastly an outline of how the 4×4 determinant method is applied to basic geometric problems is described. This article will provide, theoretical foundations for the 4×4 determinant method in computer graphics and geometric modelling.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02153665
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    On geodesic properties of polygons relevant to linear time triangulation (1989)
    Springer
    The visual computer 5 (1989), S. 68-74 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Geodesic properties ; Simple polygons ; Triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Triangulating a simple polygon ofn vertices inO(n) time is one of the main open problems in computational geometry. The fastest algorithm to date, due to Tarjan and van Wyk, runs inO(n log logn), but several classes of simple polygons have been shown to admit linear time traingulation. Famous examples of such classes are: star-shaped, monotone, spiral, edge visible, and weakly externally visible polygons. The notion of geodesic paths is used here to characterize all classes of polygons for which linear time triangulation algorithms are known. First we introduce a new class of polygons,palm polygons, which subsumes many known classes of polygons for which linear time triangulation algorithms exist, and present a linear time algorithm for triangulating polygons in this class. Then a class of polygons,crab polygons, is defined and shown to contain all classes of existing polygons for which linear time triangulation algorithms are known. As a byproduct of this characterization, a new, very simple linear time algorithm for triangulating star-shaped polygons is obtained.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901482
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    Computing correct Delaunay triangulations (1991)
    Springer
    Computing 47 (1991), S. 43-49 
    Details
    ISSN: 1436-5057
    Keywords: 51-04 ; 68Q25 ; 68R10 ; Computational geometry ; Voronoi diagram ; Delaunay triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung In den letzten Jahren hat die praktische Berechnung von Delaunay-Triangulationen bzw. Voronoi-Diagrammen große Aufmerksamkeit erfahren, da sie wichtige grundlegende Konzepte für geometrische Algorithmen darstellen. In dieser technischen Notiz betrachten wir das Problem ihrer numerisch stabilen Berechnung. Hierzu nehmen wir an, daß die generierenden Punkte Gitterpunkte eines quadratischenM×M-Gitters in der Ebene sind. Abhängig vonM bestimmen wir die notwendige Wortlänge zur Durchführung ganzzahliger Arithmetik, die es erlaubt, Delaunay-Triangulationen exakt zu berechnen. Die Analyse wird für dieL 1-,L 2- undL ∞-Metrik durchgeführt.
    Notes: Abstract In recent years the practical computation of Delaunay triangulations, resp. Voronoi diagrams has received a lot of attention in the literature. While the Delaunay triangulation is an important basic tool in geometric optimization algorithms, it is nontrivial to achieve a numerically stable computer implementation. In this technical note we assume that all generating points are grid points of a regularM byM lattice in the plane. Depending onM we derive the necessary word length a binary computer must have for integer representation in order to obtain exact Delaunay triangulations. This analysis is carried out for theL 1-,L 2- andL ∞-metric.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02242021
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    Robot motion planning and the single cell problem in arrangements (1994)
    Springer
    Journal of intelligent and robotic systems 11 (1994), S. 45-65 
    Details
    ISSN: 1573-0409
    Keywords: Computational geometry ; robotics ; arrangements ; motion planning
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract Robot motion planning has become a central topic in robotics and has been studied using a variety of techniques. One approach, followed mainly in computational geometry, aims to develop combinatorial, nonheuristic solutions to motion-planning problems. This direction is strongly related to the study of arrangements of algebraic curves and surfaces in low-dimensional Euclidean space. More specifically, the motion-planning problem can be reduced to the problem of efficiently constructing a single cell in an arrangement of curves or surfaces. We present the basic terminology and the underlying ideas of the approach. We describe past work and then survey a series of recent results in exact motion planning with three degrees of freedom and the related issues of the complexity and construction of a single cell in certain arrangements of surface patches in three-dimensional space.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01258293
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    Lines in space: Combinatorics and algorithms (1996)
    Springer
    Algorithmica 15 (1996), S. 428-447 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Lines in space ; Plücker coordinates ; ε-Nets
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Questions about lines in space arise frequently as subproblems in three-dimensional computational geometry. In this paper we study a number of fundamental combinatorial and algorithmic problems involving arrangements ofn lines in three-dimensional space. Our main results include: 1. A tight Θ(n 2) bound on the maximum combinatorial description complexity of the set of all oriented lines that have specified orientations relative to then given lines. 2. A similar bound of Θ(n 3) for the complexity of the set of all lines passing above then given lines. 3. A preprocessing procedure usingO(n 2+ɛ) time and storage, for anyε〉0, that builds a structure supportingO(logn)-time queries for testing if a line lies above all the given lines. 4. An algorithm that tests the “towering property” inO(n 2+ɛ) time, for anyε〉0; don given red lines lie all aboven given blue lines? The tools used to obtain these and other results include Plücker coordinates for lines in space andε-nets for various geometric range spaces.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01955043
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity (1995)
    Springer
    Algorithmica 13 (1995), S. 301-312 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Computer graphics ; Data structures ; Dynamic visibility problem ; Hidden surface elimination
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We investigate three-dimensional visibility problems for scenes that consist ofn non-intersecting spheres. The viewing point moves on a flightpath that is part of a “circle at infinity” given by a planeP and a range of angles {α(t)¦tε[0∶1]} ⊂ [0∶2π]. At “time”t, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angleα(t) (orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time0(n + k + p) logn), wheren is the number of spheres in the scene;p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190509
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    Edge-skeletons in arrangements with applications (1986)
    Springer
    Algorithmica 1 (1986), S. 93-109 
    Details
    ISSN: 1432-0541
    Keywords: Arrangements of planes ; Power diagrams ; Computational geometry ; Asymptotic complexity ; Dynamic data structures ; Perturbation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An edge-skeleton in an arrangementA(H) of a finite set of planes inE 3 is a connected collection of edges inA(H). We give a method that constructs a skeleton inO(√n logn) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams inE 2 and space cutting trees inE 3. We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840438
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    Characterizing and recognizing the visibility graph of a funnel-shaped polygon (1995)
    Springer
    Algorithmica 14 (1995), S. 27-51 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Funnel-shaped polygon ; Visibility graph ; Characterizing and recognizing visibility graphs ; Weakly triangulated graph ; Perfect graph
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A funnel, which is notable for its fundamental role in visibility algorithms, is defined as a polygon that has exactly three convex vertices, two of which are connected by a boundary edge. In this paper we investigate the visibility graph of a funnel which we call an F-graph. We first present two characterizations of an F-graph, one of whose sufficiency proof itself is a linear time Real RAM algorithm for drawing a funnel on the plane that corresponds to an F-graph. We next give a linear-time algorithm for recognizing an F-graph. When the algorithm recognizes an F-graph, it also reports one of the Hamiltonian cycles defining the boundary of its corresponding funnel. This recognition algorithm takes linear time even on a RAM. We finally show that an F-graph is weakly triangulated and therefore perfect, which agrees with the fact that perfect graphs are related to geometric structures.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01300372
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    A faster divide-and-conquer algorithm for constructing delaunay triangulations (1987)
    Springer
    Algorithmica 2 (1987), S. 137-151 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Voronoi diagram ; L p metric ; Computational geometry ; Average-case complexity ; Analysis of algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its Θ(n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn≤216, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL p metric for 1〈p≤∞.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840356
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space (1987)
    Springer
    Algorithmica 2 (1987), S. 367-402 
    Details
    ISSN: 1432-0541
    Keywords: Robotics ; Motion planning ; Computational geometry ; Configuration space
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present here a new and efficient algorithm for planning collision-free motion of a line segment (a rod or a “ladder”) in two-dimensional space amidst polygonal obstacles. The algorithm uses a different approach than those used in previous motion-planning techniques, namely, it calculates the boundary of the (three-dimensional) space of free positions of the ladder, and then uses this boundary for determining the existence of required motions, and plans such motions whenever possible. The algorithm runs in timeO(K logn) =O(n 2 logn) wheren is the number of obstacle corners and whereK is the total number of pairs of obstacle walls or corners of distance less than or equal to the length of the ladder. The algorithm has thus the same complexity as the best previously known algorithm of Leven and Sharir [5], but if the obstacles are not too cluttered together it will run much more efficiently. The algorithm also serves as an initial demonstration of the viability of the technique it uses, which we expect to be useful in obtaining efficient motion-planning algorithms for other more complex robot systems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840368
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    Equispreading tree in Manhattan distance (1996)
    Springer
    Algorithmica 16 (1996), S. 316-338 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Steiner tree ; Manhattan distance ; VLSI ; CAD ; Clock routing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The equispreading tree on the plane with Manhattan distance, which is a Steiner tree such that all paths from the root to all leaves have the same length, is analyzed. This problem is not only fundamental in computational geometry but also critical for equidistant routings in VLSI clock design. Several characteristics for the trees are discussed together with an algorithm constructing equispreading trees in the bottom-up fashion. This algorithm achieves linear time and space complexity with respect to the number of leaves, and minimizes the path length from the root to leaves. Furthermore, this paper shows that the shortest-path-length equispreading trees are related to the smallest enclosing circles in Manhattan distance.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01955680
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    Staircase visibility and computation of kernels (1995)
    Springer
    Algorithmica 14 (1995), S. 1-26 
    Details
    ISSN: 1432-0541
    Keywords: Restricted orientation geometry ; Computational geometry ; Polygons ; Kernel problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Let $$\mathcal{O}$$ be some set of orientations, that is, $$\mathcal{O} \subseteq [0^\circ ,360^\circ ]$$ . We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in $$\mathcal{O}$$ . We call such curves $$\mathcal{O}$$ -staircases. Two points p andq in a polygonP are said to $$\mathcal{O}$$ -see each other if an $$\mathcal{O}$$ -staircase fromp toq exists that is completely contained inP. The $$\mathcal{O}$$ -kernel of a polygonP is then the set of all points which $$\mathcal{O}$$ -see all other points. The $$\mathcal{O}$$ -kernel of a simple polygon can be obtained as the intersection of all {θ}-kernels, with θ∈ $$\mathcal{O}$$ . With the help of this observation we are able to develop an $$O(n\log \left| \mathcal{O} \right|)$$ algorithm to compute the $$\mathcal{O}$$ -kernel of a simple polygon, for finite $$\mathcal{O}$$ . We also show how to compute theexternal $$\mathcal{O}$$ -kernel of a polygon in optimal time $$O(n + \left| \mathcal{O} \right|)$$ . The two algorithms are combined to compute the ( $$\mathcal{O}$$ -kernel of a polygon with holes in time $$O(n^2 + n\left| \mathcal{O} \right|)$$ .
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01300371
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    An efficient algorithm for finding the CSG representation of a simple polygon (1993)
    Springer
    Algorithmica 10 (1993), S. 1-23 
    Details
    ISSN: 1432-0541
    Keywords: Constructive solid geometry ; Computational geometry ; Boundary representation ; Monotone boolean formulae ; Incremental convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an object explicitly but represent its interior only implicitly, and constructive solid geometry representations, which model a complex object, surface and interior together, as a boolean combination of simpler objects. Because neither representation is good for all applications, conversion between the two is often necessary. We consider the problem of converting boundary representations of polyhedral objects into constructive solid geometry (CSG) representations. The CSG representations for a polyhedronP are based on the half-spaces supporting the faces ofP. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practicalO(n logn) algorithm for doing this boundary-to-CSG conversion for a simple polygon ofn sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01908629
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    Geometric knapsack problems (1993)
    Springer
    Algorithmica 10 (1993), S. 399-427 
    Details
    ISSN: 1432-0541
    Keywords: Knapsack problems ; Computational geometry ; Convexity ; Dynamic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following “fence enclosure” problem: given a setS ofn points in the plane with valuesv i ≥ 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the “value” of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowingS to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of at mostM connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. We also provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01769706
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    A workbench for computational geometry (1994)
    Springer
    Algorithmica 11 (1994), S. 404-428 
    Details
    ISSN: 1432-0541
    Keywords: Algorithms ; Computational geometry ; Implementation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe the design and implementation of a workbench for computational geometry. We discuss issues arising from this implementation, including comparisons of different algorithms for constant factors, code size, and ease of implementation. The workbench is not just a library of computational geometry algorithms and data structures, but is designed as a geometrical programming environment, providing tools for: creating, editing, and manipulating geometric objects; demonstrating and animating geometric algorithms; and, most importantly, for implementing and maintaining complex geometric algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187021
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    An improved technique for output-sensitive hidden surface removal (1994)
    Springer
    Algorithmica 11 (1994), S. 469-484 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Hidden surface removal ; Ray shooting
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We derive a new output-sensitive algorithm for hidden surface removal in a collection ofn triangles, viewed from a pointz such that they can be ordered in an acyclic fashion according to their nearness toz. Ifk is the combinatorial complexity of the outputvisibility map, then we obtain a sophisticated randomized algorithm that runs in (randomized) timeO(n4/3 log2.89 n +k 3/5 n 4/5 + δ for anyδ 〉 0. The method is based on a new technique for tracing the visible contours using ray shooting.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293267
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    A provably fast linear-expected-time maxima-finding algorithm (1994)
    Springer
    Algorithmica 11 (1994), S. 501-524 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Maxima ; Probabilistic analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In a recent paper Bentleyet al. [1] presented some fast (low-multiplicative constants) linear-expected-time algorithms for finding the maxima ofN points chosen independently identically distributed (i.i.d.) from a Component Independent (CI) distribution. They also presented another algorithm, the Move-To-Front (MTF) algorithm, which empirical evidence suggests runs faster than the other algorithms. They conjectured that the MTF algorithm runs inN+o(N) expected time. In this paper we prove their conjecture forN points chosen i.i.d. from any two-dimensional distribution. The proof mixes probabilistic and amortized techniques.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189991
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Point placement algorithms for Delaunay triangulation of polygonal domains (1994)
    Springer
    Algorithmica 12 (1994), S. 1-17 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Polygonal domain ; Finite-element mesh generation ; Edge-free circle ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377180
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    An optimal algorithm for the on-line closest-pair problem (1994)
    Springer
    Algorithmica 12 (1994), S. 18-29 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Closest pair ; Point location ; Centroid ; Amortization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give an algorithm that computes the closest pair in a set ofn points ink-dimensional space on-line, inO(n logn) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision ofk-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377181
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    Ray shooting in polygons using geodesic triangulations (1994)
    Springer
    Algorithmica 12 (1994), S. 54-68 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray-shooting ; Triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO(√ logn) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377183
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors (1994)
    Springer
    Algorithmica 12 (1994), S. 421-435 
    Details
    ISSN: 1432-0541
    Keywords: Spanning tree ; Steiner tree ; Heuristic algorithm ; Computational geometry ; Rectilinear distance ; Nearest neighbor ; Geographic nearest neighbor ; Decomposable search problem ; Range tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n 2 log n) toO(n log2 n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188713
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons (1987)
    Springer
    Algorithmica 2 (1987), S. 209-233 
    Details
    ISSN: 1432-0541
    Keywords: Triangulation ; Simple polygon ; Visibility ; Shortest paths ; Ray shooting ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840360
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    O(log logn)-time integer geometry on the CRCW PRAM (1995)
    Springer
    Algorithmica 14 (1995), S. 52-69 
    Details
    ISSN: 1432-0541
    Keywords: PRAM ; Computational geometry ; Highly parallelizable problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study problems in computational geometry on PRAMs under the assumption that input objects are specified by points withO(logn)-bit coordinates, or, equivalently, with polynomially bounded integer coordinates. We show that in this setting many geometric problems can be solved in time O(log logn). The following five specific problems are investigated:closest pair of points, intersection of convex polygons, intersection of manhattan line segments, dominating set, andlargest empty square. Algorithms solving them are developed which operate in time O(log logn) on the arbitrary CRCW PRAM. The number of processors used is eitherO(n) orO(n logn).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01300373
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    A linear-time algorithm for constructing a circular visibility diagram (1995)
    Springer
    Algorithmica 14 (1995), S. 203-228 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Circular visibility ; Planar partition ; Trapezoidal decomposition ; Point visibility ; Simple polygon ; Amortized
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract To computer circular visibility inside a simple polygon, circular arcs that emanate from a given interior point are classified with respect to the edges of the polygon they first intersect. Representing these sets of circular arcs by their centers results in a planar partition called the circular visibility diagram. AnO(n) algorithm is given for constructing the circular visibility diagram for a simple polygon withn vertices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01206329
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    Optimal parallel algorithms for rectilinear link-distance problems (1995)
    Springer
    Algorithmica 14 (1995), S. 261-289 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Algorithms and data structures ; Parallel computation ; Link distance ; Rectilinear polygons
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We provide optimal parallel solutions to several link-distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). LetP be a trapezoided rectilinear simple polygon withn vertices. InO(logn) time usingO(n/logn) processors we can optimally compute: 1. Minimum réctilinear link paths, or shortest paths in theL 1 metric from any point inP to all vertices ofP. 2. Minimum rectilinear link paths from any segment insideP to all vertices ofP. 3. The rectilinear window (histogram) partition ofP. 4. Both covering radii and vertex intervals for any diagonal ofP. 5. A data structure to support rectilinear link-distance queries between any two points inP (queries can be answered optimally inO(logn) time by uniprocessor). Our solution to 5 is based on a new linear-time sequential algorithm for this problem which is also provided here. This improves on the previously best-known sequential algorithm for this problem which usedO(n logn) time and space.5 We develop techniques for solving link-distance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques, for example, to compute (on a CREW PRAM) optimally the link diameter, the link center, and the central diagonal of a rectilinear polygon.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01206332
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    Electronic Resource
    Electronic Resource
    Efficient ray shooting and hidden surface removal (1994)
    Springer
    Algorithmica 12 (1994), S. 30-53 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting ; Multilevel data structures ; Hidden surface removal ; Output-sensitive
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study the ray-shooting problem for three special classes of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n 2+ɛ) preprocessing, for any fixedɛ 〉 0, withO(logn) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that usesOn 4+ɛ) preprocessing and has a query time ofO(logn). We use the ray-shooting structure for curtains to obtain an algorithm for computing the view of a set of nonintersecting prolyhedra. For any ɛ 〉 0, we can obtain an algorithm with running time $$O(n^{1 + \varepsilon } \sqrt k )$$ , wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377182
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees (1996)
    Springer
    Algorithmica 15 (1996), S. 82-102 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Topological sweep ; Plane sweep ; Region representation ; Boundary extraction ; Active borders ; Region quadtrees ; Computer graphics ; Image Processing ; Geographic information systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A variant of the plane-sweep paradigm known as topological sweep is adapted to solve geometric problems involving two-dimensional regions when the underlying representation is a region quadtree. The utility of this technique is illustrated by showing how it can be used to extract the boundaries of a map inO(M) space andO(Mα(M)) time, whereM is the number of quadtree blocks in the map, andα(·) is the (extremely slowly growing) inverse of Ackerman's function. The algorithm works for maps that contain multiple regions as well as holes. The algorithm makes use of active objects (in the form of regions) and an active border. It keeps track of the current position in the active border so that at each step no search is necessary. The algorithm represents a considerable improvement over a previous approach whose worst-case execution time is proportional to the product of the number of blocks in the map and the resolution of the quadtree (i.e., the maximum level of decomposition). The algorithm works for many different quadtree representations including those where the quadtree is stored in external storage.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01942608
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    Electronic Resource
    Electronic Resource
    Parallel algorithms for arrangements (1996)
    Springer
    Algorithmica 15 (1996), S. 104-125 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Arrangement problem ; Incremental algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log* n) time andn 2/logn processors. We generalize this to obtain anO (logn log* n)-time algorithm usingn d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01941684
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 52
    Electronic Resource
    Electronic Resource
    Sweep methods for parallel computational geometry (1996)
    Springer
    Algorithmica 15 (1996), S. 126-153 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Constructive solid geometry ; Hidden-line elimination ; Plane sweeping
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give efficient parallel algorithms for a number of problems from computational geometry by using versions of parallel plane sweeping. We illustrate our approach with a number of applications, which include: General hidden-surface elimination (even if the overlap relation contains cycles). CSG boundary evaluation. Computing the contour of a collection of rectangles. Hidden-surface elimination for rectangles. There are interesting subproblems that we solve as a part of each parallelization. For example, we give an optimal parallel method for building a data structure for line-stabbing queries (which, incidentally, improves the sequential complexity of this problem). Our algorithms are for the CREW PRAM, unless otherwise noted.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01941685
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    Electronic Resource
    Electronic Resource
    Optimal cooperative search in fractional cascaded data structures (1996)
    Springer
    Algorithmica 15 (1996), S. 154-171 
    Details
    ISSN: 1432-0541
    Keywords: Parallel computing ; Fractional cascading ; PRAM ; Search ; Cooperative search ; Point location ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total sizen. The search consists of locating a key in the catalogs along a path. In this paper we show how to preprocess a variety of fractional cascaded data structures whose underlying graph is a tree so that searching can be done efficiently in parallel. The preprocessing takesO(logn) time withn/logn processors on an EREW PRAM. For a balanced binary tree, cooperative search along root-to-leaf paths can be done inO((logn)/logp) time usingp processors on a CREW PRAM. Both of these time/processor constraints are optimal. The searching in the fractional cascaded data structure can be either explicit, in which the search path is specified before the search starts, or implicit, in which the branching is determined at each node. We apply this technique to a variety of geometric problems, including point location, range search, and segment intersection search.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01941686
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    Electronic Resource
    Electronic Resource
    A subexponential bound for linear programming (1996)
    Springer
    Algorithmica 16 (1996), S. 498-516 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Combinatorial optimization ; Linear programming ; Smallest enclosing ball ; Smallest enclosing ellipsoid ; Randomized incremental algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a simple randomized algorithm which solves linear programs withn constraints andd variables in expected $$\min \{ O(d^2 2^d n),e^{2\sqrt {dIn({n \mathord{\left/ {\vphantom {n {\sqrt d }}} \right. \kern-\nulldelimiterspace} {\sqrt d }})} + O(\sqrt d + Inn)} \}$$ time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input); to be precise, the algorithm computes the lexicographically smallest nonnegative point satisfyingn given linear inequalities ind variables. The expectation is over the internal randomizations performed by the algorithm, and holds for any input. In conjunction with Clarkson's linear programming algorithm, this gives an expected bound of $$O(d^2 n + e^{O(\sqrt {dInd} )} ).$$ The algorithm is presented in an abstract framework, which facilitates its application to several other related problems like computing the smallest enclosing ball (smallest volume enclosing ellipsoid) ofn points ind-space, computing the distance of twon-vertex (orn-facet) polytopes ind-space, and others. The subexponential running time can also be established for some of these problems (this relies on some recent results due to Gärtner).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01940877
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 55
    Electronic Resource
    Electronic Resource
    Visibility of disjoint polygons (1986)
    Springer
    Algorithmica 1 (1986), S. 49-63 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Computer graphics ; Robotics ; Visibility ; Hidden-line Elimination ; Visibility graph ; Shortest path
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n 2) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n 2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n 2) time, improving earlierO(n 2 logn) results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840436
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 56
    Electronic Resource
    Electronic Resource
    Geometric complexity of some location problems (1986)
    Springer
    Algorithmica 1 (1986), S. 193-211 
    Details
    ISSN: 1432-0541
    Keywords: Location problem ; 1-line center ; Maximum gap ; Computational geometry ; Lower bound
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a set ofn demand points with weightW i ,i = 1,2,...,n, in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An Ω(n logn) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840442
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 57
    Electronic Resource
    Electronic Resource
    Using geometry to solve the transportation problem in the plane (1995)
    Springer
    Algorithmica 13 (1995), S. 442-461 
    Details
    ISSN: 1432-0541
    Keywords: Transportation problem ; Scaling ; Voronoi diagrams ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetU andV be two sets of points in the plane, where ¦U¦=k,¦V¦=ℓ, andn=k+ℓ. These two sets of points induce a directed complete bipartite graph in which the points represent nodes and an edge is directed from each node inU to each node in K Each edge is given a cost equal to the distance between the corresponding nodes measured by some metricd on the plane. We consider thetransportation problem on such a graph. We present an 0(n2,5 logn logN) algorithm, whereN is the magnitude of the largest supply or demand. The algorithm uses some fundamental results of computational geometry and scaling of supplies and demands. The algorithm is valid for the ι1 metric, the ι2 metric, and the ι∞ metric. The running time for the ι1 and ι∞ metrics can be improved to 0(n2(logn)3 logN).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190848
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    Algorithms for bichromatic line-segment problems and polyhedral terrains (1994)
    Springer
    Algorithmica 11 (1994), S. 116-132 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Line-segment intersection ; Segment trees ; Lines in space ; Polyhedral terrains ; Deterministic and randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments andn red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182771
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    Variations on ray shooting (1994)
    Springer
    Algorithmica 11 (1994), S. 133-145 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting ; Half-plane range searching ; ES-trees
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We solve some problems related toray shooting in the plane, such as finding the first object hit by a query ray or counting the number of objects intersected by the query line. Our main results are an algorithm for finding the first hit when the objects are lines, and an algorithm for the case when the objects are segments. If the segments form simple polygons, this information can be used for reducing the complexity of the algorithms. The algorithms are efficient in space and in query time. Moreover, they are simple and therefore of practical use.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182772
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    Parallel computational geometry (1988)
    Springer
    Algorithmica 3 (1988), S. 293-327 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Data structures
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line segment intersections, triangulating simple polygons, minimizing a circumscribing triangle, and recursive data-structures for three-dimensional queries.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762120
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    Decomposition and intersection of simple splinegons (1988)
    Springer
    Algorithmica 3 (1988), S. 473-485 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Curves ; Simplicity testing ; Intersection detection ; Monotone decomposition ; Convex decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A splinegon is a polygon whose edges have been replaced by “well-behaved” curves. We show how to decompose a simple splinegon into a union of monotone pieces and into a union of differences of unions of convex pieces. We also show how to use a fast triangulation algorithm to test whether two given simple splinegons intersect. We conclude with examples of splinegons that make the extension of algorithms from polygons to splinegons difficult.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762127
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    Parallel algorithms for some functions of two convex polygons (1988)
    Springer
    Algorithmica 3 (1988), S. 535-548 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Convex polygons ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Let P andQ be two convex,n-vertex polygons. We consider the problem of computing, in parallel, some functions ofP andQ whenP andQ are disjoint. The model of parallel computation we consider is the CREW-PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PRAM havingn 1/k processors can compute the following functions in O(k1+ɛ) time: (i) the common tangents betweenP andQ, and (ii) the distance betweenP andQ (and hence a straight line separating them). The positive constant ɛ can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762130
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    Primitives for the manipulation of three-dimensional subdivisions (1989)
    Springer
    Algorithmica 4 (1989), S. 3-32 
    Details
    ISSN: 1432-0541
    Keywords: Three-dimensional cell complexes ; Data structures ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Algorithms for manipulating three-dimensional cell complexes are seldom implemented due to the lack of a suitable data structure for representing them. Such a data structure is proposed here along with the primitive operations necessary to make it useful. Applications of the structure are also given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553877
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    Electronic Resource
    Electronic Resource
    A linear-time algorithm for linearL 1 approximation of points (1989)
    Springer
    Algorithmica 4 (1989), S. 77-96 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Modified pruning technique ; LinearL 1 approximation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we present a linear-time algorithm for approximating a set ofn points by a linear function, or a line, that minimizes theL 1 norm. The algorithmic complexity of this problem appears not to have been investigated, although anO(n 3) naive algorithm can be easily obtained based on some simple characteristics of an optimumL 1 solution. Our linear-time algorithm is optimal within a constant factor and enables us to use linearL 1 approximation of many points in practice. The complexity ofL 1 linear approximation of a piecewise linear function is also touched upon.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553880
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 65
    Electronic Resource
    Electronic Resource
    On the geodesic voronoi diagram of point sites in a simple polygon (1989)
    Springer
    Algorithmica 4 (1989), S. 109-140 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Voronoi diagrams ; Geodesic metric ; Simple polygons ; Shortest paths
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a simple polygon withn sides in the plane and a set ofk point “sites” in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal “geodesic” distance inside the polygon as the metric. We describe anO((n + k) log(n + k) logn)-time algorithm for solving this problem and sketch a fasterO((n + k) log(n + k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553882
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    Generation of configuration space obstacles: The case of moving algebraic curves (1989)
    Springer
    Algorithmica 4 (1989), S. 157-172 
    Details
    ISSN: 1432-0541
    Keywords: Robot motion planning ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present algebraic algorithms to generate the boundary of planar configuration space obstacles arising from the translatory motion of objects among obstacles. Both the boundaries of the objects and obstacles are given by segments of algebraic plane curves.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553884
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    Fast heuristic algorithms for rectilinear steiner trees (1989)
    Springer
    Algorithmica 4 (1989), S. 191-207 
    Details
    ISSN: 1432-0541
    Keywords: Steiner trees ; Rectilinear metric ; Heuristic algorithms ; Computational geometry ; Average case analysis ; VLSI design
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A fundamental problem in circuit design is how to connectn points in the plane, to make them electrically common using the least amount of wire. The tree formed, a Steiner tree, is usually constructed with respect to the rectilinear metric. The problem is known to be NP-complete; an extensive review of proposed heuristics is given. An early algorithm by Hanan is shown to have anO(n logn) time implementation using computational geometry techniques. The algorithm can be modified to do sequential searching inO(n 2) total time. However, it is shown that the latter approach runs inO(n 3/2) expected time, forn points selected from anm×m grid. Empirical results are presented for problems up to 10,000 points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553886
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    An efficient algorithm for maxdominance, with applications (1989)
    Springer
    Algorithmica 4 (1989), S. 221-236 
    Details
    ISSN: 1432-0541
    Keywords: Analysis of algorithms ; Computational geometry ; Tree computations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a planar setS ofn points,maxdominance problems consist of computing, for everyp εS, some function of the maxima of the subset ofS that is dominated byp. A number of geometric and graph-theoretic problems can be formulated as maxdominance problems, including the problem of computing a minimum independent dominating set in a permutation graph, the related problem of finding the shortest maximal increasing subsequence, the problem of enumerating restricted empty rectangles, and the related problem of computing the largest empty rectangle. We give an algorithm for optimally solving a class of maxdominance problems. A straightforward application of our algorithm yields improved time bounds for the above-mentioned problems. The techniques used in the algorithm are of independent interest, and include a linear-time tree computation that is likely to arise in other contexts.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553888
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    Electronic Resource
    Electronic Resource
    A new algorithm for the largest empty rectangle problem (1990)
    Springer
    Algorithmica 5 (1990), S. 65-73 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Algorithms ; Computational complexity ; Largest empty rectangle problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A rectangleA and a setS ofn points inA are given. We present a new simple algorithm for the so-called largest empty rectangle problem, i.e., the problem of finding a maximum area rectangle contained inA and not containing any point ofS in its interior. The computational complexity of the presented algorithm isO(n logn + s), where s is the number of possible restricted rectangles considered. Moreover, the expected performance isO(n · logn).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840377
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    Parallel geometric algorithms on a mesh-connected computer (1990)
    Springer
    Algorithmica 5 (1990), S. 155-177 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Mesh-connected computer ; Multipoint location ; Voronoi diagrams
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that a number of geometric problems can be solved on a √n × √n mesh-connected computer (MCC) inO(√n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires Ω(√n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. TheO(√n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840383
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    A fast algorithm for computing sparse visibility graphs (1990)
    Springer
    Algorithmica 5 (1990), S. 201-214 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Visibility graph ; Shortest path
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract AnO(¦E¦log2 n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n 2)-time andO(n 2)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840385
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    Electronic Resource
    Electronic Resource
    Dynamic fractional cascading (1990)
    Springer
    Algorithmica 5 (1990), S. 215-241 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Linear lists ; Dynamic data structures ; Amortized complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The problem of searching for a key in many ordered lists arises frequently in computational geometry. Chazelle and Guibas recently introduced fractional cascading as a general technique for solving this type of problem. In this paper we show that fractional cascading also supports insertions into and deletions from the lists efficiently. More specifically, we show that a search for a key inn lists takes timeO(logN +n log logN) and an insertion or deletion takes timeO(log logN). HereN is the total size of all lists. If only insertions or deletions have to be supported theO(log logN) factor reduces toO(1). As an application we show that queries, insertions, and deletions into segment trees or range trees can be supported in timeO(logn log logn), whenn is the number of segments (points).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840386
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 73
    Electronic Resource
    Electronic Resource
    Internal and external algorithms for the points-in-regions problem—the inside join of geo-relational algebra (1990)
    Springer
    Algorithmica 5 (1990), S. 251-276 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Point location ; Planar subdivisions ; Plane-sweep ; Divide-and-conquer ; External algorithms ; Join ; Geo-databases ; Geo-relational algebra
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the problem of collectively locating a set of points within a set of disjoint polygonal regions when neither for points nor for regions preprocessing is allowed. This problem arises in geometric database systems. More specifically it is equivalent to computing theinside join of geo-relational algebra, a conceptual model for geo-data management. We describe efficient algorithms for solving this problem based on plane-sweep and divide-and-conquer, requiringO(n(logn) +t) andO(n(log2 n) +t) time, respectively, andO(n) space, wheren is the total number of points and edges, and (is the number of reported (point, region) pairs. Since the algorithms are meant to be practically useful we consider as well as the internal versions-running completely in main memory-versions that run internally but use much less than linear space and versions that run externally, that is, require only a constant amount of internal memory regardless of the amount of data to be processed. Comparing plane-sweep and divide-and-conquer, it turns out that divide-and-conquer can be expected to perform much better in the external case even though it has a higher internal asymptotic worst-case complexity. An interesting theoretical by-product is a new general technique for handling arbitrarily large sets of objects clustered on a singlex-coordinate within a planar divide-and-conquer algorithm and a proof that the resulting “unbalanced” dividing does not lead to a more than logarithmic height of the tree of recursive calls.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840388
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 74
    Electronic Resource
    Electronic Resource
    Computational geometry in a curved world (1990)
    Springer
    Algorithmica 5 (1990), S. 421-457 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Splinegon ; Curve algorithm ; Convexity ; Monotonicity ; Intersection ; Kernel ; diameter decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840397
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    Electronic Resource
    Electronic Resource
    Some chain visibility problems in a simple polygon (1990)
    Springer
    Algorithmica 5 (1990), S. 485-507 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Simple polygon ; Visibility ; Linear-time algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, the notions of convex chain visibility and reflex chain visibility of a simple polygonP are introduced, and some optimal algorithms concerned with convex- and reflex-chain visibility problems are described. For a convex-chain visibility problem, two linear-time algorithms are exhibited for determining whether or notP is visible from a given convex chain; one is the turn-checking approach and the other is the decomposition approach based on checking edge visibilities. We also present a linear-time algorithm for finding, if any, all maximal convex chains of a given polygonP from whichP is visible, where a maximal convex chain is a convex chain which does not properly include any other convex chains. It can be made by showing that there can be at most four visible maximal convex chains inP with an empty kernel. By similar arguments, we show that the same problems for reflex chain visibility can be easily solved in linear time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840400
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 76
    Electronic Resource
    Electronic Resource
    Searching for empty convex polygons (1990)
    Springer
    Algorithmica 5 (1990), S. 561-571 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Empty convex subsets ; Analysis of algorithms ; Combinatorial geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear-time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r〉 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840404
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 77
    Electronic Resource
    Electronic Resource
    An optimal algorithm for the boundary of a cell in a union of rays (1990)
    Springer
    Algorithmica 5 (1990), S. 573-590 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Combinatorial geometry ; Union of half-lines
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study a cell of the subdivision induced by a union ofn half-lines (or rays) in the plane. We present two results. The first one is a novel proof of theO(n) bound on the number of edges of the boundary of such a cell, which is essentially of methodological interest. The second is an algorithm for constructing the boundary of any cell, which runs in optimal Θ(n logn) time. A by-product of our results are the notions of skeleton and of skeletal order, which may be of interest in their own right.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840405
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 78
    Electronic Resource
    Electronic Resource
    Moving a disc between polygons (1991)
    Springer
    Algorithmica 6 (1991), S. 182-191 
    Details
    ISSN: 1432-0541
    Keywords: Motion planning ; Polygonal obstacles ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An algorithm is given for finding a collision-free path for a disc between a collection of polygons havingn corners in total. The polygons are fixed and can be preprocessed. A query specifies the radiusr of the disc to be moved and the start and destination points of the center of the disc. The answer whether a feasible path exists is given in timeO(logn). Returning a feasible path is done in additional time proportional to the length of the description of the path. Preprocessing time isO(n logn) and space complexity isO(n).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759040
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    AnO(n logn) plane-sweep algorithm forL 1 andL ∞ Delaunay triangulations (1991)
    Springer
    Algorithmica 6 (1991), S. 207-221 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Plane-sweep algorithm ; Voronoi diagram ; L 1 metric ; L ∞ metric ; Computational geometry ; Minimal spanning tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract TheDelaunay diagram on a set of points in the plane, calledsites, is the straight-line dual graph of the Voronoi diagram. When no degeneracies are present, the Delaunay diagram is a triangulation of the sites, called theDelaunay triangulation. When degeneracies are present, edges must be added to the Delaunay diagram to obtain a Delaunay triangulation. In this paper we describe an optimalO(n logn) plane-sweep algorithm for computing a Delaunay triangulation on a possibly degenerate set of sites in the plane under theL 1 metric or theL ∞ metric.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759042
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    Order-k voronoi diagrams of sites with additive weights in the plane (1991)
    Springer
    Algorithmica 6 (1991), S. 490-521 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Voronoi diagrams ; Geömetric transformation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract It is shown that the order-k Voronoi diagram of n sites with additive weights in the plane has at most (4k−2)(n−k) vertices, (6k−3)(n−k) edges, and (2k−1)(n−itk) + 1 regions. These bounds are approximately the same as the ones known for unweighted order-k Voronoi diagrams. Furthermore, tight upper bounds on the number of edges and vertices are given for the case that every weighted site has a nonempty region in the order-1 diagram. The proof is based on a new algorithm for the construction of these diagrams which generalizes a plane-sweep algorithm for order-1 diagrams developed by Steven Fortune. The new algorithm has time-complexityO(k 2 n logn) and space-complexityO(kn). It is the only nontrivial algorithm known for constructing order-kc Voronoi diagrams of sites withadditive weights. It is fairly simple and of practical interest also in the special case of unweighted sites.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759056
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    Convex hulls of objects bounded by algebraic curves (1991)
    Springer
    Algorithmica 6 (1991), S. 533-553 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Algorithms and data structures ; Algebraic geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an0(n ·d o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759058
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    Finding a minimal cover for binary images: An optimal parallel algorithm (1991)
    Springer
    Algorithmica 6 (1991), S. 624-657 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Image compression ; Minimal square covers ; Orthogonal polygons ; Parallel prefix computations ; Minimal vertex covers ; Bipartite graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a black-and-white image, represented by an array of √n × √n binary-valued pixels, we wish to cover the black pixels with aminimal set of (possibly overlapping) maximal squares. It was recently shown that obtaining aminimum square cover for a polygonal binary image with holes is NP-hard. We derive an optimal parallel algorithm for theminimal square cover problem, which for any desired computation timeT in [logn,n] runs on an EREW-PRAM with (n/T) processors. The cornerstone of our algorithm is a novel data structure, the cover graph, which compactly represents the covering relationships between the maximal squares of the image. The size of the cover graph is linear in the number of pixels. This algorithm has applications to problems in VLSI mask generation, incremental update of raster displays, and image compression.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759065
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    On partitioning rectilinear polygons into star-shaped polygons (1991)
    Springer
    Algorithmica 6 (1991), S. 771-800 
    Details
    ISSN: 1432-0541
    Keywords: Polygon decomposition ; Star-shaped polygons ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. We then use this algorithm to obtain anO(n logn) approximation algorithm for partitioning simple rectilinear polygons into star-shaped polygons with the size of the partition being at most six times the optimum.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759071
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    Computational geometry algorithms for the systolic screen (1991)
    Springer
    Algorithmica 6 (1991), S. 734-761 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Clustering ; Convex hull ; Digitized pictures ; Hulls ; Maxima ; Mesh-of-processors ; Parallel computing ; Separability ; Systolic array ; Visibility ; Voronoi diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Adigitized plane Π of sizeM is a rectangular √M × √M array of integer lattice points called pixels. A √M × √M mesh-of-processors in which each processorP ij represents pixel (i,j) is a natural architecture to store and manipulate images in Π; such a parallel architecture is called asystolic screen. In this paper we consider a variety of computational-geometry problems on images in a digitized plane, and present optimal algorithms for solving these problems on a systolic screen. In particular, we presentO(√M)-time algorithms for determining all contours of an image; constructing all rectilinear convex hulls of an image (peeling); solving the parallel and perspective visibility problem forn disjoint digitized images; and constructing the Voronoi diagram ofn planar objects represented by disjoint images, for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., allL p metrics). These algorithms implyO(√M)-time solutions to a number of other geometric problems: e.g., rectangular visibility, separability, detection of pseudo-star-shapedness, and optical clustering. One of the proposed techniques also leads to a new parallel algorithm for determining all longest common subsequences of two words.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759069
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    Optimal randomized parallel algorithms for computational geometry (1992)
    Springer
    Algorithmica 7 (1992), S. 91-117 
    Details
    ISSN: 1432-0541
    Keywords: Randomized ; Parallel algorithm ; Computational geometry ; Point location ; Triangulation ; Trapezoidal decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present parallel algorithms for some fundamental problems in computational geometry which have a running time ofO(logn) usingn processors, with very high probability (approaching 1 asn → ∞). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758753
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    Electronic Resource
    Electronic Resource
    Optimal parallel algorithms for point-set and polygon problems (1992)
    Springer
    Algorithmica 7 (1992), S. 3-23 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Parallel algorithms ; Polygon ; All nearest-neighbor problem ; Kernel problem ; Convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758749
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 87
    Electronic Resource
    Electronic Resource
    Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers (1992)
    Springer
    Algorithmica 7 (1992), S. 51-75 
    Details
    ISSN: 1432-0541
    Keywords: Hypercube ; Parallel algorithms ; Convex hull ; Domination ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper gives hypercube algorithms for some simple problems involving geometric properties of sets of points. The properties considered emphasize aspects of convexity and domination. Efficient algorithms are given for both fine- and medium-grain hypercube computers, including a discussion of implementation, running times and results on an Intel iPSC hypercube, as well as theoretical results. For both serial and parallel computers, sorting plays an important role in geometric algorithms for determining simple properties, often being the dominant component of the running time. Since the time required to sort data on a hypercube computer is still not fully understood, the running times of some of our algorithms for unsorted data are not completely determined. For both the fine- and medium-grain models, we show that faster expected-case running time algorithms are possible for point sets generated randomly. Our algorithms are developed for sets of planar points, with several of them extending to sets of points in spaces of higher dimension.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758751
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 88
    Electronic Resource
    Electronic Resource
    L 1 shortest paths among polygonal obstacles in the plane (1992)
    Springer
    Algorithmica 8 (1992), S. 55-88 
    Details
    ISSN: 1432-0541
    Keywords: Shortest paths ; Voronoi diagrams ; Rectilinear paths ; Wire routing ; Fixed orientation metrics ; Continuous Dijkstra algorithm ; Computational geometry ; Extremal graph theory
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for computingL 1 shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(nɛ−1/2 log2 n) time andO(nɛ−1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL 1 Voronoi diagram for source points that lie among a collection of polygonal obstacles.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758836
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 89
    Electronic Resource
    Electronic Resource
    Line-segment intersection reporting in parallel (1992)
    Springer
    Algorithmica 8 (1992), S. 119-144 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Line-segment intersection reporting ; Segment tree ; PRAM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give a parallel algorithm for line-segment intersection reporting in the plane. It runs in timeO(((n +k) logn log logn)/p) usingp processors on a concurrent-read-exclusive-write (CREW)-PRAM, wheren is the number of line segments,k is the number of intersections, andp ≤n +k.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758839
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    An efficient algorithm for one-step planar compliant motion planning with uncertainty (1992)
    Springer
    Algorithmica 8 (1992), S. 195-208 
    Details
    ISSN: 1432-0541
    Keywords: Motion planning ; Compliant motion ; Uncertainty ; Robotics ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Uncertainty in the execution of robot motion plans must be accounted for in the geometric computations from which plans are obtained, especially in the case where position sensing is inaccurate. We give anO(n 2 logn) algorithm to find a single commanded motion direction that will guarantee a successful motion in the plane from a specified start to a specified goal whenever such a one-step motion is possible. The plans account for uncertainty in the start position and in robot control, and anticipate that the robot may stick on or slide along obstacle surfaces with which it comes in contact. This bound improves on the best previous bound by a quadratic factor, and is achieved in part by a new analysis of the geometric complexity of the backprojection of the goal as a function of commanded motion direction.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758843
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs (1992)
    Springer
    Algorithmica 8 (1992), S. 177-194 
    Details
    ISSN: 1432-0541
    Keywords: Matching ; Computational geometry ; Bottleneck optimization problem ; Relative neighborhood graph
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E r k ) whereE r k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE r 17 . We also prove that ¦E r k ¦ 〈 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n 2) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n 1.5 log0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n 2 +n 1.5 log0.5 n).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758842
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    On the parallel-decomposability of geometric problems (1992)
    Springer
    Algorithmica 8 (1992), S. 209-231 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Mesh-connected arrays of processors ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n 1/d ) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen 〉p. The goal we seek is to achieve, when solving a problem of sizen 〉p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen 〉p as when solving a problem of sizep.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758844
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    Output-sensitive generation of the perspective view of isothetic parallelepipeds (1992)
    Springer
    Algorithmica 8 (1992), S. 257-283 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Hidden-line elimination ; Perspective view ; Isothetic rectangles ; Parallelepipeds ; Fractional cascading ; Segment tree ; Range tree ; Dominance relation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a new hidden-line elemination technique for displaying the perspective view of a scene of three-dimensional isothetic parallelepipeds (3D-rectangles). We assume that the 3D-rectangles are totally ordered based upon the dominance relation of occlusion. The perspective view is generated incrementally, starting with the closest 3D-rectangle and proceeding away from the view point. Our algorithm is scene-sensitive and uses0((n +d) logn log logn) time, wheren is the number of 3D-rectangles andd is the number of edges of the display. This improves over the heretofore best known technique. The primary data structure is an efficient alternative to dynamic fractional cascading for use with augmented segment and range trees when the universe is fixed beforehand. It supports queries inO((logn +k) log logn) time, wherek is the size of the response, and insertions and deletions inO(logn log logn) time, all in the worst case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758847
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    Probing a scene of nonconvex polyhedra (1992)
    Springer
    Algorithmica 8 (1992), S. 321-342 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Geometric probing ; Polyhedral scenes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show, in this paper, how the exact shapes of a class of polyhedral scenes can be computed by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra with no collinear edges, no coplanar faces, and such that no edge is contained in the supporting plane of a nonincident face. The basic step of our method is a strategy for probing a single simple polygon with no collinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that allows us to compute the exact shape of a simple polygon with no collinear edges by means of at most3n — 3 probes, wheren is the number of edges of the polygon. This is optimal in the worst case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in planar sections of a scene of polyhedra of the class above to find out, in turn, each edge of the scene. If the scene consists ofk polyhedra with altogethern faces andm edges, we show that $$\tfrac{{10}}{3}n\left( {m + k} \right) - 2m - 3k$$ probes are sufficient to compute the exact shapes of the polyhedra.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758849
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    Electronic Resource
    Electronic Resource
    Quasi-optimal upper bounds for simplex range searching and new zone theorems (1992)
    Springer
    Algorithmica 8 (1992), S. 407-429 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Range searching ; Space-time tradeoff
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ℜd so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n 〈m 〈n d ), then we show that it is possible to answer any query inO(n 1+ɛ/m 1/d ) query time afterO(m 1+ɛ) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n d+ɛ) storage for any fixed ɛ 〉 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758854
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 96
    Electronic Resource
    Electronic Resource
    Simultaneous inner and outer approximation of shapes (1992)
    Springer
    Algorithmica 8 (1992), S. 365-389 
    Details
    ISSN: 1432-0541
    Keywords: Polygonal approximation ; Algorithmic paradigms ; Shape approximation ; Computational geometry ; Implicit complexity parameters ; Banach-Mazur metric
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer 〉 0,s 〉 0 satisfy $$sQ' \subseteq P \subseteq rQ''$$ . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... 〈-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k −2). We give anO(n 2 log2 n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)〈-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758852
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 97
    Electronic Resource
    Electronic Resource
    Approximate motion planning and the complexity of the boundary of the union of simple geometric figures (1992)
    Springer
    Algorithmica 8 (1992), S. 391-406 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Motion planning ; Boundary complexity ; Combinatorial geometry ; Analysis of algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of Ω(n 2), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/ɛcrit + 1)n(logn)2), wherea ≥b are the lengths of the sides of a rectangle and ɛcrit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758853
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 98
    Electronic Resource
    Electronic Resource
    Minimum-link paths among obstacles in the plane (1992)
    Springer
    Algorithmica 8 (1992), S. 431-459 
    Details
    ISSN: 1432-0541
    Keywords: Link distance ; Shortest paths ; Motion planning ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(Eα(n) log2 n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and α(n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758855
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 99
    Electronic Resource
    Electronic Resource
    The slab dividing approach to solve the EuclideanP-Center problem (1993)
    Springer
    Algorithmica 9 (1993), S. 1-22 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; NP-completeness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Givenn demand points on the plane, the EuclideanP-Center problem is to findP supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, isO(n 2 p−1· logn). In this paper, we present an algorithm with time complexityO(n 0(√P)).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185335
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 100
    Electronic Resource
    Electronic Resource
    Parallel methods for visibility and shortest-path problems in simple polygons (1992)
    Springer
    Algorithmica 8 (1992), S. 461-486 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Data structures ; Visibility ; Polygons ; CREW PRAM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758856
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...