- The Shortest Path with Increasing Chords in a Simple Polygon
2022/02/24 by Mart Hagedoorn, Irina Kostitsyna, Hagedoorn, Mart +1 · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer network #Computer science #Constrained Shortest Path First #Data Management and Algorithms #Dijkstra's algorithm #Euclidean shortest path #FOS: Computer and information sciences #Geometry #Graph #K shortest path routing #Mathematics #Monotone polygon #Optimization and Packing Problems #Path (computing) #Polygon (computer graphics) #Shortest Path Faster Algorithm #Shortest path problem #Simple polygon #Yen's algorithm
- Counting Polygon Triangulations is Hard
2019/01/01 by David Eppstein · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Computational Geometry and Mesh Generation #Mathematics and Applications #Advanced Mathematical Theories and Applications #Polygon (computer graphics) #Combinatorics #Simple (philosophy) #Rectilinear polygon #Simple polygon #Polygon covering #Computer science #Mathematics #Monotone polygon #Geometry
- An Approximation Algorithm for the Art Gallery Problem
2016/07/19 by Édouard Bonnet, Tillmann Miltzow · 1 citation
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Optimization and Packing Problems #Complexity and Algorithms in Graphs #Combinatorics #Simple polygon #Guard (computer science) #General position #Polygon (computer graphics) #Mathematics #Simple (philosophy) #Point (geometry) #Line segment #Integer (computer science) #Algorithm #Discrete mathematics #Regular polygon #Computer science #Geometry
- Finding equal-diameter triangulations in polygons
2014/06/08 by András Bezdek, Ted Bisztriczky · 1 citation
Computer Science · Mathematics · #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Constructive #Data Management and Algorithms #Digital Image Processing Techniques #Geometry #Mathematics #Perimeter #Polygon (computer graphics) #Polygon covering #Rectilinear polygon #Regular polygon #Simple (philosophy) #Simple polygon #Star-shaped polygon
- Approximate Guarding of Monotone and Rectilinear Polygons
2012/06/05 by Erik Krohn, Erik A. Krohn, Bengt J. Nilsson · 2 citations
Computer Science · Engineering · Mathematics · #Algorithm #Approximation algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Convex optimization #Convex set #Discrete mathematics #Geometry #Graph #Guard (computer science) #Mathematics #Monotone polygon #Optimization and Packing Problems #Point in polygon #Polygon (computer graphics) #Polygon covering #Polygon mesh #Rectilinear polygon #Regular polygon #Robotic Path Planning Algorithms #Simple polygon #Star-shaped polygon #Theory of computation #Vertex (graph theory)
- An exact algorithm for minimizing vertex guards on art galleries
2011/03/01 by Marcelo C. Couto, Pedro J. de Rezende, Cid C. de Souza · 1 citation
Computer Science · Environmental Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Image and Video Retrieval Techniques #Remote Sensing and LiDAR Applications #Discretization #Point in polygon #Polygon (computer graphics) #Vertex (graph theory) #Mathematics #Algorithm #Polygon covering #Regular polygon #Simple polygon #Combinatorics #Computer science #Rectilinear polygon #Geometry #Graph
- Inapproximability Results for Guarding Polygons and Terrains
2001/09/01 by Stephan Eidenbenz, S. Eidenbenz, C. Stamm +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Geometry #Graph #Guard (computer science) #Mathematics #Point in polygon #Polygon (computer graphics) #Regular polygon #Set (abstract data type) #Set cover problem #Simple polygon #Time complexity #Vertex (graph theory) #Vertex cover
- A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time
2001/01/01 by Nancy M. Amato, N. M. Amato, Michael T. Goodrich +3 · 1 citation
Computer Science · Engineering · Mathematics · #3D Shape Modeling and Analysis #Algorithm #Artificial intelligence #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Dijkstra's algorithm #Freivalds' algorithm #Mathematics #Polygon (computer graphics) #Polygon covering #Preprocessor #Randomized algorithm #Regular polygon #Robotics and Sensor-Based Localization #SIMPLE algorithm #Shortest path problem #Simple (philosophy) #Simple polygon #Time complexity
- Art Gallery and Illumination Problems
2000/01/01 by Jorge Urrutia · 2 citations
Computer Science · Engineering · Mathematics · #3D Shape Modeling and Analysis #Art #Art gallery #Combinatorics #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Digital Image Processing Techniques #Epistemology #Exhibition #Geometry #Guard (computer science) #Mathematics #Optics #Painting #Philosophy #Physics #Plane (geometry) #Polygon (computer graphics) #Regular polygon #Simple (philosophy) #Simple polygon #Visibility #Visual arts
- THE VISIBILITY COMPLEX
1996/09/01 by Michel Pocchiola, Gert Vegter · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Robotic Path Planning Algorithms #Visibility #Visibility polygon #Disjoint sets #Mathematics #Complement (music) #Polygon (computer graphics) #Combinatorics #Visibility graph #Subdivision #Set (abstract data type) #Plane (geometry) #Regular polygon #Triangulation #Discrete mathematics #Simple polygon #Computer science #Geometry
- COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
1995/09/01 by Yaw-Ling Lin, Steven Skiena · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Optimization and Search Problems #Robotic Path Planning Algorithms #Visibility graph #Combinatorics #Visibility polygon #Visibility #Mathematics #Pathwidth #Vertex (graph theory) #Discrete mathematics #Polygon (computer graphics) #Indifference graph #Maximal independent set #Planar graph #Outerplanar graph #Vertex cover #1-planar graph #Time complexity #Graph #Chordal graph #Simple polygon #Computer science #Line graph #Regular polygon #Geometry #Optics
- Generating triangulations at random
1994/07/01 by Peter Epstein, Jörg-Rüdiger Sack · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Advanced Graph Theory Research #Combinatorics #Polygon (computer graphics) #Simple (philosophy) #Simple polygon #Polygon covering #Mathematics #Rectilinear polygon #Random graph #Discrete mathematics #Graph #Algorithm #Computer science #Monotone polygon #Geometry
- Slicing an ear using prune-and-search
1993/09/01 by Hossam ElGindy, Hazel Everett, Godfried Toussaint · 1 citation
Computer Science · Engineering · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Diagonal #Geometry #Mathematics #Monotone polygon #Physics #Polygon (computer graphics) #Robotic Path Planning Algorithms #Robotics and Sensor-Based Localization #SIMPLE algorithm #Simple (philosophy) #Simple polygon #Slicing #Time complexity #Triangulation
- Three-coloring the vertices of a triangulated simple polygon
1992/04/01 by Ali A. Kooshesh, A.A. Kooshesh, B.M.E. Moret +1 · 1 citation
Computer Science · Mathematics · #Algorithm #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #Computer science #Cover (algebra) #Geography #Geometry #Mathematics #Observer (physics) #Polygon (computer graphics) #Regular polygon #Robotic Path Planning Algorithms #Set (abstract data type) #Set cover problem #Simple (philosophy) #Simple polygon #Terrain #Time complexity #Visibility
- Polygon triangulation inO(n log logn) time with simple data structures
1992/04/01 by David Kirkpatrick, David G. Kirkpatrick, Maria Klawe +2 · 1 citation
Computer Science · Mathematics · #Algorithm #Binary logarithm #Bounded function #Combinatorics #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #Computer science #Data Management and Algorithms #Data structure #Geometry #Graph #Mathematics #Partition (number theory) #Polygon (computer graphics) #Polygon covering #Regular polygon #Simple polygon #Time complexity #Triangulation #Vertex (graph theory) #Visibility polygon
- Triangulating a simple polygon in linear time
1991/09/01 by Bernard Chazelle · 2 citations
Computer Science · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Constrained Delaunay triangulation #Data Management and Algorithms #Data Visualization and Analytics #Delaunay triangulation #Diagonal #Discrete mathematics #Geometry #Mathematics #Minimum-weight triangulation #Point set triangulation #Polygon (computer graphics) #Polygon covering #Regular polygon #Simple (philosophy) #Simple polygon #Star-shaped polygon #Time complexity #Triangulation
- A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
1991/07/01 by Raimund Seidel · 2 citations
Computer Science · Environmental Science · Mathematics · #Algorithm #Binary logarithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Data Management and Algorithms #Freivalds' algorithm #Geometry #Graph #Line segment #Logarithm #Mathematics #Plane (geometry) #Polygonal chain #Randomized algorithm #Regular polygon #Remote Sensing and LiDAR Applications #Running time #SIMPLE algorithm #Set (abstract data type) #Shortest path problem #Simple (philosophy) #Simple polygon #Time complexity
- A simple algorithm for computing the smallest enclosing circle
1991/02/01 by Sven Skyum · 1 citation
Computer Science · Environmental Science · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computational geometry #Computer science #Convex polygon #Digital Image Processing Techniques #Geometry #Mathematics #Point (geometry) #Polygon (computer graphics) #Polygon covering #Regular polygon #Remote Sensing and LiDAR Applications #SIMPLE algorithm #Simple (philosophy) #Simple polygon #Voronoi diagram
- A fast las vegas algorithm for triangulating a simple polygon
1989/10/01 by Kenneth L. Clarkson, Robert E. Tarjan, Christopher J. Van Wyk · 4 citations
Computer Science · Engineering · Mathematics · #3D Shape Modeling and Analysis #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Convex set #Data Management and Algorithms #Geometry #Las vegas #Mathematics #Polygon (computer graphics) #Polygon covering #Randomized algorithm #Regular polygon #SIMPLE algorithm #Simple (philosophy) #Simple polygon #Star-shaped polygon
- An O(nlog log n)-Time Algorithm for Triangulating a Simple Polygon
1988/02/01 by Robert E. Tarjan, Christopher J. Van Wyk · 10 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Optimization and Search Problems #Robotics and Sensor-Based Localization #Simple polygon #Combinatorics #Polygon covering #Diagonal #Mathematics #Polygon (computer graphics) #Partition (number theory) #Simple (philosophy) #Computational geometry #Time complexity #Binary logarithm #Vertex (graph theory) #Triangulation #Algorithm #SIMPLE algorithm #Sorting #Monotone polygon #Computer science #Graph #Geometry
- Computational complexity of art gallery problems
1986/03/01 by D. Lee, A. Lin · 5 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Image and Video Retrieval Techniques #Artificial Intelligence in Games #Simple polygon #Polygon (computer graphics) #Combinatorics #Vertex (graph theory) #Computational complexity theory #Mathematics #Computational geometry #Simple (philosophy) #Computer science #Vertex cover #Time complexity #Discrete mathematics #Algorithm #Regular polygon #Geometry #Graph
- A new linear algorithm for triangulating monotone polygons
1984/03/01 by Godfried T Toussaint, Godfried T. Toussaint · 1 citation
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Cartesian coordinate system #Code (set theory) #Combinatorics #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #Computer science #Enhanced Data Rates for GSM Evolution #Geometry #Mathematics #Monotone polygon #Point in polygon #Polygon (computer graphics) #Rectilinear polygon #Robotic Path Planning Algorithms #Simple (philosophy) #Simple polygon
- Some NP-hard polygon decomposition problems
1983/03/01 by Joseph O’Rourke, Kenneth J. Supowit · 3 citations
Computer Science · Engineering · Mathematics · #Digital Image Processing Techniques #Computational Geometry and Mesh Generation #graph theory and CDMA systems #Computational complexity theory #Polygon (computer graphics) #Decomposition #Regular polygon #Mathematical proof #Visibility polygon #Satisfiability #Boolean satisfiability problem #Mathematics #Transformation (genetics) #Computer science #Simple polygon #Computational geometry #Combinatorics #Algorithm #Discrete mathematics #Theoretical computer science #Geometry
- An efficient algorithm for decomposing a polygon into star-shaped polygons
1981/01/01 by David Avis, D. Avis, G.T. Toussaint +1 · 2 citations
Computer Science · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computational geometry #Computer science #Data Management and Algorithms #Decomposition #Digital Image Processing Techniques #Efficient algorithm #Geometry #Mathematical analysis #Mathematics #Plane (geometry) #Point in polygon #Polygon (computer graphics) #Polygon covering #Rectilinear polygon #Regular polygon #Simple polygon #Star (game theory)