Back to my home page.

On Point Covers of c-Oriented Polygons

Frank Nielsen

Abstract:
Let S be any family of n c-oriented polygons of the 2-dimensional Euclidean plane E2, i.e., bounded intersection of halfplanes whose normal directions of edges belong to a fixed 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 require so that each object contains at least one of those points. We prove that τ(S)≤ Γ(2,c)φ(S) log2c-1(φ(S )+1), where Γ(2,c) is the Gallai number of pairwise intersecting c-oriented polygons. Our bound collapses to τ(S)=O(Γ(2,c)φ(S)) if objects are of 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 Ed proving that Γ(2,c)=O(α)d, Γ(2,c)≤ dd and Γ(2,c)≤ (3d3/2)d respectively.
  Key words: computational geometry, output-sensitive algorithms, precision-sensitive heuristics , transversal and packing numbers.
Ask me the PS paper (758 Kb size, 10 pages, 5 figures).
 
The original publication is available at Elsevier Science.
 
doi: 10.1016/S0304-3975(00)00227-9
Bibtex entry:

@Article{n-pcop:2001
	, author =	"Frank Nielsen"
	, title =	"On Point Covers of $c$-Oriented Polygons"
	, journal =	"Theo. Comp. Sci."
	, volume =	265
	, number =	"1--2"
	, year =	2001
	, pages =	"17-29"
	, doi = {10.1016/S0304-3975(00)00227-9}
 }
Related publications:
© Copyright notice.
Last updated, 2003.