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
Löhner Extensions and improvements of the advancing front grid generation technique
Chen et al. Computing shortest paths among curved obstacles in the plane
Chiang et al. Two-point Euclidean shortest path queries in the plane
Bose et al. A visibility representation for graphs in three dimensions
US20250014278A1 (en) Pointcloud processing, especially for use with building intelligence modelling (bim)
Pach et al. Combinatorial geometry and its algorithmic applications: The Alcalá lectures
Barnsley et al. Fractal tilings from iterated function systems
Arroyo Ohori et al. An evaluation and classification of n D topological data structures for the representation of objects in a higher-dimensional GIS
US7426455B1 (en) Optimal boolean set operation generation among polygon-represented regions
Di Luna et al. Meeting in a polygon by anonymous oblivious robots
Black et al. Monotone paths on cross-polytopes
Goodrich et al. Stabbing parallel segments with a convex polygon
Forberg et al. Generalization of 3D building data based on scale-spaces
Kisfaludi-Bak et al. A quadtree, a steiner spanner, and approximate nearest neighbours in hyperbolic space
Hoffmann et al. A universality theorem for allowable sequences with applications
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
Ramnath New approximations for the rectilinear steiner arborescence problem [vlsi layout]
Jan et al. Shortest path-planning on polygonal surfaces with O (nlog n) time
Brown A fast algorithm for selective refinement of terrain meshes
Nishat et al. The hamiltonian path graph is connected for simple s, t paths in rectangular grid graphs
Bauernöppel et al. An ω (nd) lower bound on the number of cell crossings for weighted shortest paths in d-dimensional polyhedral structures