Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Separating translates in the plane: Combinatorial bounds and an algorithm

Jurek Czyzowicz1, Hazel Everett2 and Jean-Marc Robert3

(1)  Dép. d'informatique, Université du Québec à Hull, C.P. 1250, J8X 2X7 Succ. B, Hull, Canada
(2)  Dép. de mathématiques et d'informatique, Université du Québec à Montréal, C.P. 8888, H3C 3P8 Succ. Centre-Ville, Montréal, Canada
(3)  Dép. d'informatique et de mathématique, Université du Québec à Chicoutimi, 555 boul. de l'Université, G7H 2B1 Chicoutimi, Canada
Abstract
In this paper, we establish two combinatorial bounds related to the separation problem for sets of n pairwise disjoint translates of convex objects: 1) there exists a line which separates one translate from at least n — coradicn translates, for some constant c that depends on the ldquoshaperdquo of the translates and 2) there is a function f such that there exists a line with orientation THgr or f(THgr) which separates one translate from at least lceil3nrceil/4-4 translates, for any orientation THgr (f is defined only by the ldquoshaperdquo of the translate). We also present an O(n log (n+k)+k) time algorithm for finding a translate which can be separated from the maximum number of translates amongst sets of n pairwise disjoint translates of convex k-gons.
This research was supported by FCAR, FODAR and NSERC.
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.113 • Server: mpweb02
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)