Opening book details…
Can I read On Point Covers of C-oriented Polygons on EtoBox?
On Point Covers of C-oriented Polygons by Frank Nielsen is a Computer Science article available to read on EtoBox.
What is On Point Covers of C-oriented Polygons about?
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 ÿxed collection of c distinct directions. Let (S) denote the packing number of S, that is the maximum number of pairwise disjoint objects of S. Let (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 (S)6G(2; c) (S) log c-1 2 ( (S)+1), where G(2; c) is the Gallai number of pairwise intersecting c-oriented polygons. Our bound collapses to (S) = O(G(2; c) (S)) if objects are more or less of the same size. We describe a t(n; c) + O(nc log (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) = (nc) for -fat c-oriented polytopes, translates or homothets of E d proving that G(2; c) = O( ) d , G(2; c)6d d and G(2; c)6(3d 3=2 ) d respectively.
Who reads On Point Covers of C-oriented Polygons?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Frank Nielsen
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)
- Published
- 2001
- Language
- EN
- Field
- Computer Science (Physical Sciences)