An Optimal Algorithm for Finding the Kernel of a Polygon

DOI10.1145/322139.322142zbMath0403.68051MaRDI QIDQ4188754

No author found.

Publication date: 1979

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2142/74090

zbMATH Keywords

Algorithms; Computational Complexity; Kernel of a Polygon

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

52-04: Software, source code, etc. for problems pertaining to convex and discrete geometry

52A10: Convex sets in (2) dimensions (including convex curves)

68R99: Discrete mathematics in relation to computer science

Related Items

Determining Weak Visibility of a Polygon from an Edge in Parallel, TURNING SHAPE DECISION PROBLEMS INTO MEASURES, SEARCHING A POLYGONAL REGION FROM THE BOUNDARY, SUCCESSIVE MAPPINGS: AN APPROACH TO POLYGONAL MESH SIMPLIFICATION WITH GUARANTEED ERROR BOUNDS, OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS, PLANAR STRONG VISIBILITY, Open Guard Edges and Edge Guards in Simple Polygons, GUARDING ART GALLERIES BY GUARDING WITNESSES, Finding the shortest boundary guard of a simple polygon, On \(k\)-convex polygons, LR-visibility in polygons, Linear-time algorithms for weakly-monotone polygons, Minimum vertex distance between separable convex polygons, Computational geometry in a curved world, Some chain visibility problems in a simple polygon, Visibility between two edges of a simple polygon, Recognizing polygons, or how to spy, On geodesic properties of polygons relevant to linear time triangulation, Maintenance of configurations in the plane, Optimal parallel algorithms for point-set and polygon problems, On the number of guard edges of a polygon, Recognizing weakly convex visible polygons, Searching and on-line recognition of star-shaped polygons., The traveling salesmanpProblem for lines in the plane, Optimally computing a shortest weakly visible line segment inside a simple polygon, Applications of a two-dimensional hidden-line algorithm to other geometric problems, Staircase visibility and computation of kernels, A linear-time algorithm for constructing a circular visibility diagram, \(\alpha\)-kernel problem with fuzzy visibility, Minimal link visibility paths inside a simple polygon, Approximate guarding of monotone and rectilinear polygons, On circularly-hidden surface removal., Multiple point visibility and related problems, High-quality surface remeshing using harmonic maps, A new triangulation-linear class of simple polygons