On point covers of \(c-\)oriented polygons

DOI10.1016/S0304-3975(00)00227-9zbMath0974.68220OpenAlexW2038103262WikidataQ128089875 ScholiaQ128089875MaRDI QIDQ5941498

Frank Nielsen

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00227-9

zbMATH Keywords

computational geometryoutput-sensitive algorithmsprecision-sensitive heuristicstransversal and packing numbers

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Piercing pairwise intersecting convex shapes in the plane, Point enclosure problem for homothetic polygons, Piercing translates and homothets of a convex body, Fast stabbing of boxes in high dimensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering boxes by points
• Optimal packing and covering in the plane are NP-complete
• On point covers of parallel rectangles
• Bounding the vertex cover number of a hypergraph
• 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
• A practical map labeling algorithm.
• Improved non-approximability results
• Approximation schemes for covering and packing problems in image processing and VLSI
• Fast approximation algorithms for a nonconvex covering problem
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Dynamic data structures for fat objects and their applications