The complexity of computing minimum separating polygons

DOI10.1016/0167-8655(93)90140-9MaRDI QIDQ4274652zbMATH OpenOpenAlexFDO

Authors Peter Eades, David Rappaport

Publication date 17 February 1994

Published in Pattern Recognition Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8655(93)90140-9

zbMATH Keywords

NP-hardfinite setsminimum separating polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Minimum polygonal separation
• scientific article; zbMATH DE number 742976
• Separating point sets in polygonal environments
• The complexity of separating points in the plane
• The complexity of separating points in the plane

Cited in

(17)

• The complexity of separating points in the plane
• Minimum polygonal separation
• Geometric Knapsack problems
• scientific article; zbMATH DE number 5592483 (Why is no real title available?)
• Exact and heuristic solutions for the prize‐collecting geometric enclosure problem
• Bounds for point recolouring in geometric graphs
• The complexity of oblivious plans for orienting and distinguishing polygonal parts
• Touring a sequence of disjoint polygons: complexity and extension
• scientific article; zbMATH DE number 1305490 (Why is no real title available?)
• scientific article; zbMATH DE number 1746653 (Why is no real title available?)
• scientific article; zbMATH DE number 3883608 (Why is no real title available?)
• Convex hulls in polygonal domains
• The complexity of separating points in the plane
• Delineating boundaries for imprecise regions
• Maintaining the minimal distance of a point set in polylogarithmic time
• Lower bounds for the number of hyperplanes separating two finite sets of points
• Geometric multicut: shortest fences for separating groups of objects in the plane

This page was built for publication: The complexity of computing minimum separating polygons

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