Nothing Special   »   [go: up one dir, main page]

Hershberger, 1989 - Google Patents

An optimal visibility graph algorithm for triangulated simple polygons

Hershberger, 1989

Document ID
15254536710738258813
Author
Hershberger J
Publication year
Publication venue
Algorithmica

External Links

Snippet

Let P be a triangulated simple polygon with n sides. The visibility graph of P has an edge between every pair of polygon vertices that can be connected by an open segment in the interior of P. We describe an algorithm that finds the visibility graph of P in O (m) time, where …
Continue reading at link.springer.com (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30958—Graphs; Linked lists
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/01—Input arrangements or combined input and output arrangements for interaction between user and computer
    • G06F3/048—Interaction techniques based on graphical user interfaces [GUI]
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T11/00—2D [Two Dimensional] image generation
    • G06T11/20—Drawing from basic elements, e.g. lines or circles
    • G06T11/206—Drawing of charts or graphs
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
    • G06T17/05—Geographic models
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
    • G06T17/20—Finite element generation, e.g. wire-frame surface description, tesselation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06K—RECOGNITION OF DATA; PRESENTATION OF DATA; RECORD CARRIERS; HANDLING RECORD CARRIERS
    • G06K9/00—Methods or arrangements for reading or recognising printed or written characters or for recognising patterns, e.g. fingerprints
    • G06K9/36—Image preprocessing, i.e. processing the image information without deciding about the identity of the image
    • G06K9/46—Extraction of features or characteristics of the image

Similar Documents

Publication Publication Date Title
Hershberger An optimal visibility graph algorithm for triangulated simple polygons
Hershberger Finding the visibility graph of a simple polygon in time proportional to its size
Asano et al. Visibility of disjoint polygons
Carr et al. Computing contour trees in all dimensions
Arge et al. External-memory algorithms for processing line segments in geographic information systems
Chen et al. Computing shortest paths among curved obstacles in the plane
Bose et al. A visibility representation for graphs in three dimensions
Barnsley et al. Fractal tilings from iterated function systems
Bishop Nonobtuse triangulations of PSLGs
Di Luna et al. Meeting in a polygon by anonymous oblivious robots
Benouamer et al. Error-free boundary evaluation using lazy rational arithmetic: a detailed implementation
Chepoi et al. Shortest path problem in rectangular complexes of global nonpositive curvature
Goodrich et al. Stabbing parallel segments with a convex polygon
Forberg et al. Generalization of 3D building data based on scale-spaces
Hoffmann et al. A universality theorem for allowable sequences with applications
Nye Random walks and Brownian motion on cubical complexes
Lee et al. Geographic knowledge discovery from Web Map segmentation through generalized Voronoi diagrams
Inkulu et al. Dynamic algorithms for visibility polygons in simple polygons
Aggarwal et al. Computing the minimum visible vertex distance between two polygons: Preliminar version
Wang et al. Algorithms for Halfplane Coverage and Related Problems
Li et al. Finding the shortest path between two points in a simple polygon by applying a rubberband algorithm
Ramnath New approximations for the rectilinear steiner arborescence problem [vlsi layout]
Kisfaludi-Bak et al. A quadtree, a steiner spanner, and approximate nearest neighbours in hyperbolic space
Jan et al. Shortest path-planning on polygonal surfaces with O (nlog n) time
Brown A fast algorithm for selective refinement of terrain meshes