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)
  • Articles: DFG German National Licenses  (117)
  • Articles and Proceedings (GFZpublic)
  • Computational geometry  (117)
  • Computer Science  (117)
  • Economics
Collection
  • Articles  (117)
Source
  • Articles: DFG German National Licenses  (117)
  • Articles and Proceedings (GFZpublic)
Keywords
Publisher
Years
Topic
  • 1
    Electronic Resource
    Electronic Resource
    Some basic geometric test conditions in terms of Plücker coordinates and Plücker coefficients (1997)
    Springer
    The visual computer 13 (1997), S. 29-41 
    Details
    ISSN: 1432-2315
    Keywords: Key words: Computer graphics ; Geometric modeling ; Computer-aided geometric design ; Computational geometry ; Homogeneous geometry ; Plücker coordinates ; 4×4 Determinant method ; Projective geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s003710050087
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    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
  • 3
    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
  • 4
    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
  • 5
    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
  • 6
    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
  • 7
    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
  • 8
    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
  • 9
    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
  • 10
    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
  • 11
    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: Symmetry detection ; Congruity problem ; Algorithm design ; Graph theory ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We propose a simple and efficient general algorithm for determining both rotational and involutional symmetries of polyhedra. It requiresO(m 2) time and usesO(m) space, wherem 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
  • 12
    Electronic Resource
    Electronic Resource
    Tetrahedral finite element mesh generation from NURBS solid models (1996)
    Springer
    Engineering with computers 12 (1996), S. 211-223 
    Details
    ISSN: 1435-5663
    Keywords: Computational geometry ; Delaunay tetrahedrization ; Finite element meshing ; Octrees
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics , Technology
    Notes: Abstract In this paper, the development and the implementation of a tetrahedral meshing algorithm for generation of finite element meshes from NURBS solid models is presented. The meshing algorithm is based on a Delaunay technique, and makes use of some spatial data structures. The algorithm is capable of generating both uniform and varying size four-node and ten-node tetrahedral meshes. The algorithm has been implemented in a building block approach as part of a software library. It has been used as a practical tool in engineering design processes. Several representative test cases illustrate the effectiveness of the automatic solid mesh generator.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01198735
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    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
  • 14
    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
  • 15
    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
  • 16
    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
  • 17
    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
  • 18
    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
  • 19
    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
  • 20
    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
  • 21
    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
  • 22
    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
  • 23
    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
  • 24
    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
  • 25
    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
  • 26
    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
  • 27
    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
  • 28
    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
  • 29
    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
  • 30
    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
  • 31
    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
  • 32
    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
  • 33
    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
  • 34
    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
  • 35
    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
  • 36
    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
  • 37
    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
  • 38
    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
  • 39
    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
  • 40
    Electronic Resource
    Electronic Resource
    Maximumk-covering of weighted transitive graphs with applications (1993)
    Springer
    Algorithmica 9 (1993), S. 84-100 
    Details
    ISSN: 1432-0541
    Keywords: Transitive graphs ; Network flow ; VLSI layout ; Computational geometry ; Integer sequences
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Consider a weighted transitive graph, where each vertex is assigned a positive weight. Given a positive integerk, the maximumk-covering problem is to findk disjoint cliques covering a set of vertices with maximum total weight. An 0(kn 2)-time algorithm to solve the problem in a transitive graph is proposed, wheren is the number of vertices. Based on the proposed algorithm the weighted version of a number of problems in VLSI layout (e.g.,k-layer topological via minimization), computational geometry (e.g., maximum multidimensionalk-chain), graph theory (e.g., maximumk-independent set in interval graphs), and sequence manipulation (e.g., maximum increasingk-subsequence) can be solved inO(kn 2), wheren is the input size.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185340
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Duality of constrained Voronoi diagrams and Delaunay triangulations (1993)
    Springer
    Algorithmica 9 (1993), S. 142-155 
    Details
    ISSN: 1432-0541
    Keywords: Voronoi diagram ; Delaunay triangulation ; Duality ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We introduce theconstrained Voronoi diagram of a planar straight-line graph containingn vertices or sites where the line segments of the graph are regarded as obstacles, and show that an extended version of this diagram is the dual of theconstrained Delaunay triangulation. We briefly discussO(n logn) algorithms for constructing the extended constrained Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188709
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    Fast linear expected-time algorithms for computing maxima and convex hulls (1993)
    Springer
    Algorithmica 9 (1993), S. 168-183 
    Details
    ISSN: 1432-0541
    Keywords: Maxima ; Convex hulls ; Computational geometry ; Algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper examines the expected complexity of boundary problems on a set ofN points inK-space. We assume that the points are chosen from a probability distribution in which each component of a point is chosen independently of all other components. We present an algorithm to find the maximal points usingKN + O (N1−1/K log1/K N) expected scalar comparisons, for fixedK≥ 2. A lower bound shows that the algorithm is optimal in the leading term. We describe a simple maxima algorithm that is easy to code, and present experimental evidence that it has similar running time. For fixedK ≥ 2, an algorithm computes the convex hull of the set in 2KN + O(N1−1/K log1/KN) expected scalar comparisons. The history of the algorithms exhibits interesting interactions among consulting, algorithm design, data analysis, and mathematical analysis of algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188711
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    A semidynamic construction of higher-order voronoi diagrams and its randomized analysis (1993)
    Springer
    Algorithmica 9 (1993), S. 329-356 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Dynamic algorithm ; Randomized complexity analysis ; Orderk Voronoi diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the order≤k Voronoi diagrams, can be done inO(n logn+k 3n) expected time and O(k2n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k ⌈(d+1)/2⌉+1 n ⌊(d+1)/2⌋) and space complexityO(k ⌈(d+1)/2⌉ n ⌊(d+1)/2⌋). The algorithm is simple and experimental results are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228508
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    The searching over separators strategy to solve some NP-hard problems in subexponential time (1993)
    Springer
    Algorithmica 9 (1993), S. 398-423 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; NP-hardness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator which divides the input points into two parts,A d andC d, in such a way that after solving these two subproblems withA d andC d as inputs, respectively, we can merge the respective subsolutions into an optimal solution. Let us further assume that this problem is an optimization problem. In this case our searching over separators strategy will use a separator generator to generate all possible separators. For each separator, the problem is solved by the divide-and-conquer strategy. If the separator generator is guaranteed to generate the desired separator existing in an optimal solution, our searching over separators strategy will always produce an optimal solution. The performance of our approach will critically depend upon the performance of the separator generator. It will perform well if the total number of separators generated is relatively small. We apply this approach to solve the discrete EuclideanP-median problem (DEPM), the discrete EuclideanP-center problem (DEPC), the EuclideanP-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose $$O(n^{o(\sqrt P )} )$$ algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an $$O(n^{o(\sqrt n )} )$$ algorithm for the ETSP problem, wheren is the number of input points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228511
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    Ray shooting on triangles in 3-space (1993)
    Springer
    Algorithmica 9 (1993), S. 471-494 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting on triangles ; Arrangements of hyperplanes ; 3-Space ; Plücker coordinates ; Isotopy classes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a uniform approach to problems involving lines in 3-space. This approach is based on mapping lines inR 3 into points and hyperplanes in five-dimensional projective space (Plücker space). We obtain new results on the following problems: 1. Preprocessn triangles so as to answer efficiently the query: “Given a ray, which is the first triangle hit?” (Ray- shooting problem). We discuss the ray-shooting problem for both disjoint and nondisjoint triangles. 2. Construct the intersection of two nonconvex polyhedra in an output sensitive way with asubquadratic overhead term. 3. Construct the arrangement ofn intersecting triangles in 3-space in an output-sensitive way, with asubquadratic overhead term. 4. Efficiently detect the first face hit by any ray in a set of axis-oriented polyhedra. 5. Preprocessn lines (segments) so as to answer efficiently the query “Given two lines, is it possible to move one into the other without crossing any of the initial lines (segments)?” (Isotopy problem). If the movement is possible produce an explicit representation of it.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187036
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    Constructing strongly convex approximate hulls with inaccurate primitives (1993)
    Springer
    Algorithmica 9 (1993), S. 534-560 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Epsilon Geometry ; Approximate computations ; Robust algorithms ; Strongly convex polygons ; Convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The first half of this paper introducesEpsilon Geometry, a framework for the development of robust geometric algorithms using inaccurate primitives. Epsilon Geometry is based on a very general model of imprecise computations, which includes floating-point and rounded-integer arithmetic as special cases. The second half of the paper introduces the notion of a (−ɛ)-convex polygon, a polygon that remains convex even if its vertices are all arbitrarily displaced by a distance ofɛ of less, and proves some interesting properties of such polygons. In particular, we prove that for every point set there exists a (−ɛ)-convex polygonH such that every point is at most 4ɛ away fromH. Using the tools of Epsilon Geometry, we develop robust algorithms for testing whether a polygon is (−ɛ)-convex, for testing whether a point is inside a (−ɛ)-convex polygon, and for computing a (−ɛ)-convex approximate hull for a set of points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190154
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    Algorithms for projecting points to give the most uniform distribution with applications to hashing (1993)
    Springer
    Algorithmica 9 (1993), S. 572-590 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Duality transform ; Hashing ; Intersection-reporting algorithm ; Linear-space algorithm ; Plane sweep ; Projection ; Simplex range search ; Topological walk
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents several algorithms for projecting points so as to give the most uniform distribution. Givenn points in the plane and an integerb, the problem is to find an optimal angleθ ofb equally spaced parallel lines such that points are distributed most uniformly over buckets (regions bounded by two consecutive lines). An algorithm is known only in thetight case in which the two extreme lines are the supporting lines of the point set. The algorithm requiresO(bn2 logn) time and On2+bn) space to find an optimal solution. In this paper we improve the algorithm both in time and space, based on duality transformation. Two linear-space algorithms are presented. One runs in On2+K log n+bn) time, whereK is the number of intersections in the transformed plane.K is shown to beO(@#@ n2+bn@#@) based on a new counting scheme. The other algorithm is advantageous ifb 〈 √n. It performs a simplex range search in each slab to enumerate all the lines that intersectbucket lines, and runs in O(b0.610n1.695+K logn) time. It is also shown that the problem can be solved in polynomial time even in therelaxed case. Its one-dimensional analogue is especially related to the design of an optimal hash function for a static set of keys.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190156
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    Splitting a configuration in a simplex (1993)
    Springer
    Algorithmica 9 (1993), S. 649-668 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Partition of point sets ; Assignment problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents a new method of partition, namedπ-splitting, of a point set ind-dimensional space. Given a pointG in ad-dimensional simplexT, T(G;i) is the subsimplex spanned by G and the ith facet ofT. LetS be a set ofn points inT, and letπ be a sequence of nonnegative integers π1, ..., nd+1 satisfying σ i=1 d+1 π1=n Theπ-splitter of (T, S) is a pointG inT such thatT(G;i) contains at leastπ i points ofS in its closure for everyi=1, 2, ...,d + 1. The associated dissection is the re-splitting. The existence of aπ-splitting is shown for any (T, S) andπ, and two efficient algorithms for finding such a splitting are given. One runs inO(d2n logn + d3n) time, and the other runs inO(n) time if the dimensiond can be considered as a constant. Applications of re-splitting to mesh generation, polygonal-tour generation, and a combinatorial assignment problem are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190161
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    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
  • 50
    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
  • 51
    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
  • 52
    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
  • 53
    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
  • 54
    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
  • 55
    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
  • 56
    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
  • 57
    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
  • 58
    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
  • 59
    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
  • 60
    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
  • 61
    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
  • 62
    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
  • 63
    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
  • 64
    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
  • 65
    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
  • 66
    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
  • 67
    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
  • 68
    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
  • 69
    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
  • 70
    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
  • 71
    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
  • 72
    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
  • 73
    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
  • 74
    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
  • 75
    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
  • 76
    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
  • 77
    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
  • 78
    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
  • 79
    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
  • 80
    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
  • 81
    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
  • 82
    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
  • 83
    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
  • 84
    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
  • 85
    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
  • 86
    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
  • 87
    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
  • 88
    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
  • 89
    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
  • 90
    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
  • 91
    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
  • 92
    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
  • 93
    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
  • 94
    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
  • 95
    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
  • 96
    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
  • 97
    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
  • 98
    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
  • 99
    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
  • 100
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...