An Optimal Algorithm for Finding the Kernel of a Polygon

DOI10.1145/322139.322142MaRDI QIDQ4188754zbMATH OpenOpenAlexFDO

Authors

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

AlgorithmsComputational ComplexityKernel of a Polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10)

Cited in

(52)

• Linear-time algorithms for weakly-monotone polygons
• Staircase visibility and computation of kernels
• Locked and unlocked smooth embeddings of surfaces
• GUARDING ART GALLERIES BY GUARDING WITNESSES
• Finding all weakly-visible chords of a polygon in linear time
• Determining Weak Visibility of a Polygon from an Edge in Parallel
• TURNING SHAPE DECISION PROBLEMS INTO MEASURES
• Recognizing weakly convex visible polygons
• Applications of a two-dimensional hidden-line algorithm to other geometric problems
• Arc fibrations of planar domains
• PLANAR STRONG VISIBILITY
• Detection and computation of conservative kernels of models consisting of freeform curves and surfaces, using inequality constraints
• OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
• On the axial symmetry of 2D star-shaped sets
• Minimal link visibility paths inside a simple polygon
• High-quality surface remeshing using harmonic maps
• Representing planar domains by polar parameterizations with parabolic parameter lines
• Kernel-based construction operators for Boolean sum and ruled geometry
• On geodesic properties of polygons relevant to linear time triangulation
• Guarding precise and imprecise polyhedral terrains with segments
• Maintenance of configurations in the plane
• On the number of guard edges of a polygon
• Guarding orthogonal art galleries with sliding cameras
• Approximate guarding of monotone and rectilinear polygons
• Arc-fibration kernels of arc-spline domains
• Two-guarding a rectilinear polygon
• Approximation algorithms for the two-watchman route in a simple polygon
• \(\alpha\)-kernel problem with fuzzy visibility
• SEARCHING A POLYGONAL REGION FROM THE BOUNDARY
• Recognizing polygons, or how to spy
• Optimizing generalized kernels of polygons
• On k-convex polygons
• Visibility between two edges of a simple polygon
• Computational geometry in a curved world
• Optimally computing a shortest weakly visible line segment inside a simple polygon
• On circularly-hidden surface removal.
• Some chain visibility problems in a simple polygon
• Guarding a 1.5D terrain with imprecise viewpoints
• A new triangulation-linear class of simple polygons
• Optimal parallel algorithms for point-set and polygon problems
• An O(log log n) algorithm to compute the kernel of a polygon
• Searching and on-line recognition of star-shaped polygons.
• Minimum vertex distance between separable convex polygons
• The traveling salesmanpProblem for lines in the plane
• SUCCESSIVE MAPPINGS: AN APPROACH TO POLYGONAL MESH SIMPLIFICATION WITH GUARANTEED ERROR BOUNDS
• Line-of-sight pursuit in monotone and scallop polygons
• A linear-time algorithm for constructing a circular visibility diagram
• Starshaped sets
• Finding the shortest boundary guard of a simple polygon
• Multiple point visibility and related problems
• Open guard edges and edge guards in simple polygons
• LR-visibility in polygons

This page was built for publication: An Optimal Algorithm for Finding the Kernel of a Polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4188754)