Illuminating Triangles and Quadrilaterals with Vertex Floodlights (2009)
Felipe Contreras, Jurek Czyzowicz, Nicolas Fraiji, Jorge Urrutia
We show that three π/6 vertex floodlights suffice to illuminate any triangle, and we prove that any quadrilateral can be illuminated by three π/4 vertex floodlights. 1
Algorithms for Packing Two Circles in a Convex Polygon (2009)
Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Anil Maheshwari
3
More Efficient Periodic Traversal in Anonymous Undirected Graphs (2009)
Czyzowicz, Jurek, Dobrev, Stefan, Gasieniec, Leszek, Ilcinkas, David, Jansson, Jesper, Klasing, Ralf, ...
We consider the problem of periodic graph exploration in which a mobile entity with (at most) constant memory, an agent, has to visit all $n$ nodes of an arbitrary undirected graph G in a periodic...
More Efficient Periodic Traversal in Anonymous Undirected Graphs (2009)
Czyzowicz, Jurek, Dobrev, Stefan, Gasieniec, Leszek, Ilcinkas, David, Jansson, Jesper, Klasing, Ralf, ...
We consider the problem of periodic graph exploration in which a mobile entity with (at most) constant memory, an agent, has to visit all $n$ nodes of an arbitrary undirected graph G in a periodic...
Cutting Circles into Equal Area Pieces 1 Prosenjit Bose (2008)
Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jurek Czyzowicz
We study several problems related to cutting circles into equal area pieces. Our objective is to minimize the total length of the cuts.
Jurek Czyzowicz, Gatineau Québec, Euripides Markou, Dariusz Kowalski, Andrzej Pelc
of searching for a black hole
published in Algorithmica 30, 2001, p.67–82. Circular Separability of Polygons ∗ (2008)
Jean-daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Mariette Yvinec
Two planar sets are circularly separable if there exists a circle enclosing one of the sets and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Jurek Czyzowicz, Evangelos Kranakis, Jorge Urrutia
We study a problem of dissecting a rectangle into a minimum number of pieces which may be reassembled into a square. The dissection is made using only rectilinear glass-cuts, i.e., vertical or...
On Tilable Orthogonal Polygons ∗ (2008)
György Csizmadia, Jurek Czyzowicz, Evangelos Kranakis, Eduardo Rivera-campo, Jorge Urrutia
We consider rectangular tilings of orthogonal polygons with vertices located at integer lattice points. Let G be a set of reals closed under the usual addition operation. A G-rectangle is a rectangle...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P, a flipturn involves reflecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grünbaum (1995)) showed that any polygon on n vertices...
vol., no., pp. – () The Maximum Number of Edges in a Three-Dimensional Grid-Drawing ∗ (2008)
Prosenjit Bose, Jurek Czyzowicz, Gatineau Québec Canada, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bound-ing box. The first universal lower bound on the volume of...
Efficient Computation of Throughput Values of Context-Free Languages (2008)
Didier Caucal, Jurek Czyzowicz, Wojciech Fraczak, Wojciech Rytter
Abstract. We present the first deterministic polynomial time algorithm that computes the throughput value of a given context-free language L. The language is given by a grammar G of size n, together...
Strategies for Hotlink Assignments (Extended Abstract) Prosenjit Bose (2008)
Jurek Czyzowicz, Leszek G Asieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc
\Lambda z
Cutting rectangles in equal area pieces Prosenjit Bose (2007)
Jurek Czyzowicz, Dominic Lessard
Problem 1 Let P be an axis parallel rectangle. We want to cut P in k equal area pieces such that the total length of the cuts is minimum.
Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Miguel Vargas Martin
Consider a DAG (directed acyclic graph) G = (V; E) representing a collection V of web pages connected via links E. All web pages can be reached from a designated source page, represented by a source...
Cutting Rectangles in Equal Area Pieces (2007)
Prosenjit Bose, Jurek Czyzowicz, Dominic Lessard
this paper we restrict our attention to straight line orthogonal cuts. We assume that each cut is complete in that it divides a rectangle into two pieces.
Domino Tilings of Orthogonal Polygons (2007)
Gyorgy Csizmadia, Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis, Jorge Urrutia
We consider orthogonal polygons with vertices located at integer lattice points. We show that if all of the sides of a simple orthogonal polygon without holes have odd lengths, then it cannot be...
Domino Tilings of Orthogonal Polygons (2007)
György Csizmadia, Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis, Jorge Urrutia
We consider orthogonal polygons with vertices located at integer lattice points. We show that if all of the sides of a simple orthogonal polygon without holes have odd lengths, then it cannot be...
Circular Separability ofPolygons (2007)
Mariette Yvinec, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, ...
novembre 94
Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. A three-dimensional (straight-line) grid-drawing...
Jurek Czyzowicz, A Evangelos, Kranakis Danny Krizanc, Andrzej Pelc X
In a Web site, each page v has a certain probability pv of being requested by a user. The access cost of a Web site is the sum of Pv c(r, v), of every page v, where c(r, v) is the cost of the...
Cutting Rectangles Into Equal Area Pieces Prosenjit Bose (2007)
Jurek Czyzowicz, Dominic Lessard
Problem 1 Let P be an axis parallel rectangle. We want to cut P in k equal area pieces such that the total length of the cuts is minimum.
Hee-kap Ahn, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
z Universite du Quebec a Hull.
On k-Guarding of Polygons (2007)
Patrice Belleville, Jurek Czyzowicz, Jorge Urrutia, Joseph Zaks
A polygon is called k-guardable if it is possible to find a collection G of points in the interior of the edges of P such that every point in P is visible from at least k elements of G, and such that...
Hee-kap Ahn, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Figure 1: An example of a ipturn. Given a polygon P, a ipturn involves re ecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed...
Notes about d-cuckoo hashing (2006)
Jurek Czyzowicz, Wojciech Fraczak, Feliks Welfeld
We show an upper bound for the minimal size set of keys which cannot be inserted into a d-cuckoo hashing table independently of the hashing functions and the insertion algorithm. We also discuss the...
Simultaneous Diagonal Flips in Plane Triangulations (2005)
Bose, Prosenjit, Czyzowicz, Jurek, Gao, Zhicheng, Morin, Pat, Wood, David R.
Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every $n$-vertex triangulation with at least six vertices has a simultaneous flip into a 4-connected...
Prime Normal Form and Equivalence of Simple (2005)
Grammars Cedric Bastien, Cédric Bastien, Jurek Czyzowicz, Wojciech Fraczak
A prefix-free language is a prime if it cannot be decomposed into a concatenation of two prefix-free languages. We show that we can check in polynomial time if a language generated by a simple...
Searching for a black hole in tree networks (2005)
Czyzowicz, Jurek, Kowalski, Dariusz, Markou, Euripides, Pelc, Andrzej, Higashino, Teruo
The maximum number of edges in a three-dimensional grid-drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. A three-dimensional (straight-line) grid-drawing...
The maximum number of edges in a three-dimensional grid-drawing (2003)
Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. A three-dimensional (straight-line) grid-drawing...
The maximum number of edges in a three-dimensional grid-drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
vol., no., pp.-- ()
The Maximum Number of Edges in a Three-Dimensional Grid-Drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of...
Simultaneous Diagonal Flips in Plane (2003)
Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, David R. Wood
† Research partially completed at Carleton University and McGill University
The maximum number of edges in a three-dimensional grid-drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of...
Optimal Assignment of Bookmarks to Web Pages (2002)
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Miguel Vargas Martin
yzk
Circular Separability of Polygons (2001)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Circular Separability of Polygons (2001)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Circular Separability of Polygons (2001)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Evaluation of Hotlink Assignment Heuristics for Improving Web Access (2001)
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Miguel Vargas Martin
We study the optimal hotlink assignment problem. Consider a web site as a directed graph, where each page is represented by a node and each link is represented by an edge. The resulting graph is...
Computing Largest Circles Separating Two Sets of Segments (2000)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle C separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Computing Largest Circles Separating Two Sets of Segments (2000)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle C separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. We show that any polygon on n vertices will be convex after any sequence of at most n(n 3)=2...
Hee-Kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Convex Tours of Bounded Curvature (1999)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Computing largest circles separating two sets of segments (1999)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Circular Separability of Polygons (1999)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the sets and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Near-Optimal Partitioning of Rectangles and Prisms (1999)
Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Dominic Lessard
This paper focuses on the following problems:
Near-Optimal Partitioning of Rectangles and Prisms (1999)
Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Dominic Lessard
This paper focuses on the following problems:
Jurek Czyzowicz, Ivan Stojmenovic, Jorge Urrutia
Let shape P be any simply-connected set in the plane, bounded by a Jordan curve, that is not a circular disk. We say that a set of points I on the boundary of P immobilize the shape if any rigid...
Convex Tours of Bounded Curvature. (1999)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Convex Tours of Bounded Curvature. (1999)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Discrete Realizations of Contact and Intersection Graphs (Extended Abstract) (1998)
Czyzowicz, Jurek, Kranakis, Evangelos, Krizanc, Danny, Urrutia, Jorge
Known realizations of geometric representations of graphs, like contact, intersection etc., are "continuous", in the sense that the geometric objects are drawn in Euclidean space with real numbers as...
Discrete Realizations of Contact and Intersection Graphs (Extended Abstract) (1998)
Czyzowicz, Jurek, Kranakis, Evangelos, Krizanc, Danny, Urrutia, Jorge
Known realizations of geometric representations of graphs, like contact, intersection etc., are "continuous", in the sense that the geometric objects are drawn in Euclidean space with real numbers as...
Discrete Realizations of Contact and Intersection Graphs (Extended Abstract) (1998)
Czyzowicz, Jurek, Kranakis, Evangelos, Krizanc, Danny, Urrutia, Jorge
Known realizations of geometric representations of graphs, like contact, intersection etc., are "continuous", in the sense that the geometric objects are drawn in Euclidean space with real numbers as...
Algorithms for packing two circles in a convex polygon (1998)
Jurek Czyzowicz, Evangelos Kranakis, Anil Maheshwari
Abstract. We consider algorithms for packing two circles in a given n-vertex convex polygon. The rst algorithm outputs a pair of equal non-overlapping circles of maximum radius and has running time...
Maximal Length Common Non-Intersecting Paths (1996)
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia
Given a set P n of n points on the plane labeled with the integers f1; : : : ; ng, an increasing path of P n is a sequence of points i 1 ! : : : ! i k such that the polygonal path obtained by...
Computing Largest Circles Separating Two Sets of Segments (1996)
Jean-daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Joge Urrutia, Mariette Yvinec
A circle C separates two planar sets if it en closes one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Computing Largest Circles Separating Two Sets of Segments (1995)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Computing Largest Circles Separating Two Sets of Segments (1995)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Computing Largest Circles Separating Two Sets of Segments (1995)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Computing Largest Circles Separating Two Sets of Segments (1995)
Jorge Urrutia, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, ...
A circle C separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Circular Separability of Polygons (1995)
Mariette Yvinec, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, ...
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Computing Largest Circles Separating Two Sets of Segments (1995)
Jorge Urrutia, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, ...
A circle C separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Convex Tours of Bounded Curvature (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with...
Circular Separability of Polygons (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Convex Tours of Bounded Curvature (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with...
Circular Separability of Polygons (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Convex Tours of Bounded Curvature (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with...
Circular Separability of Polygons (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Convex tours of bounded curvature (1994)
Jean-daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Jean-marc Robert, Mariette Yvinec
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Convex Tours of Bounded Curvature (1994)
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, Olivier Devillers, ...
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Convex tours of bounded curvature (1994)
Apport De Recherche, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, ...
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Jurek Czyzowicz, Eduardo Rivera-campo, Jorge Urrutia
A line L separates a set A from a collection S of plane sets if A is contained in one of the closed half-planes defined by L, while every set in S is contained in the complementary closed half-plane....
Polygon Cutting: Revisited Prosenjit Bose
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Anil Maheshwari
Abstract. Given a simple polygon P on n vertices v0; v1; : : : ; vn 1 with each edge assigned a non-negative weight w i, we show how to compute in O(n) time a segment v i b (where b is a point on the...