On point covers of c-oriented polygons

DOI10.1016/S0304-3975(00)00227-9MaRDI QIDQ5941498zbMATH OpenOpenAlexWikidataFDO

Authors 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 geometry output-sensitive algorithms precision-sensitive heuristics transversal and packing numbers

Mathematics Subject Classification ID

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

Review text

Let \(S\) be any family of \(n\) \(c\)-oriented polygons of the two-dimensional Euclidean plane \(E^{2},\) i.e., bounded intersection of halfplanes whose normal directions of edges belong to a fixed collection of \(c\) distinct directions. Let \(\phi(S)\) denote the packing number of \(S,\) that is the maximum number of pairwise disjoint objects of \(S.\) Let \(\tau(S)\) be the transversal number of \(S,\) that is the minimum number of points required so that each object contains at least one of those points. We prove that \(\tau(S)<G(2,c)\phi(S) \log_{2}^{c-1}(\phi(S)+1)\), where \(G(2,c)\) is the Gallai number of pairwise intersecting \(c\)-oriented polygons. Our bound collapses to \(\tau(S)=O(G(2,c)\phi(S))\) if objects are more or less of the same size. We describe a \(t(n,c)+O(nc\log \phi(S))\)-time algorithm with linear storage that computes such a 0-transversal, where \(t(n,c)\) is the time required to pierce pairwise intersecting \(c\)-oriented polygons. We provide linear-time algorithms \(t(n,c)=\Theta(nc)\) for \(\alpha\)-fat \(c\)-oriented polytopes, translates or homothets of \(E^{d}\) proving that \(G(2,c)=O(\alpha)^{d}\), \(G(2,c)<d^{d}\) and \(G(2,c)<(3d^{3/2})^{d}\) respectively.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: On point covers of \(c-\)oriented polygons

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