The complexity of computing minimum separating polygons

DOI10.1016/0167-8655(93)90140-9zbMATH Open0781.68113OpenAlexW2063514882MaRDI QIDQ4274652FDOQ4274652

David Rappaport, Peter Eades

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

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

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)

Cited In (14)

• Title not available (Why is that?)
• Minimum polygonal separation
• Geometric Knapsack problems
• Title not available (Why is that?)
• Exact and heuristic solutions for the prize‐collecting geometric enclosure problem
• Bounds for point recolouring in geometric graphs
• Title not available (Why is that?)
• The complexity of oblivious plans for orienting and distinguishing polygonal parts
• Touring a sequence of disjoint polygons: complexity and extension
• Title not available (Why is that?)
• Title not available (Why is that?)
• Delineating boundaries for imprecise regions
• Maintaining the minimal distance of a point set in polylogarithmic time
• 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)