Ph.D. Candidate
Computer Science at SUNY at Stony Brook
Stony Brook, NY, 11794
packer_eli at yahoo dot com
|
Eli Packer Ph.D. Candidate Computer Science at SUNY at Stony Brook Stony Brook, NY, 11794 packer_eli at yahoo dot com |
|
At present, I am a PhD candidate in the department of
Computer Science at State University of New York at Stony Brook.
I started my studies in 2003 and I am now in the final stages.
My main research interests are algorithms in general and
geometric algorithms in particular, computer graphics and software
engineering. I work in the Computational Geometry lab in Stony Brook
University under the supervision of Prof. J.S.B
Mitchell. Click here for more information on my work in Stony
Brook.
Education
Honors and Awards
Research interests, achievements and work in progress
My main interest is generating new algorithms for optimizations of geometric and graphic problems, and in
further designing and implementing them for practical use and experiments.
I am always interested in broadening my knowledge and experience in various types of such algorithms, but in
particular I focus in the following areas.
Robustness in Computational Geometry
Sensor Coverage
Surface Reconstruction
Collision Detection of Deformable Models
Publications
Journal and Conference Publications
Conference Submissions
Light Conferences
Manual Chapters
*Special thanks
to Prof. Alon Efrat for helpful advices in preparing this page
I received my Bachelor and Master of Science degrees in Computer
Science with distinction from Tel Aviv University, Israel. During these studies I
received excellence awards for study and research. I worked in
the Computational Lab of Prof. Dan Halperin,
and I was a member of the CGAL
(Computational Geometry Algorithm Library) team where I developed two software packages for CGAL that are
used today, Iterated
Snap Rounding and Largest
Empty Rectangle. My Master Thesis contains new Finite Precision
Approximation techniques.
I have 7 years of experience working for Motorola Semi-Conductor and
Orbotech Ltd., where I worked as a project leader in a VLSI
verification project and as an algorithm developer in an automatic
image inspection project, respectively. My projects were mostly written in C, C++ and Matlab, and
supported both Windows and Unix operating systems.
Below is a brief summary of the projects I am involved in.
The implementation of geometric algorithms is generally difficult because one must deal with both
precision problems and degenerate input. While these issues are
usually ignored when describing geometric algorithms in theory,
overlooking them in practice may result in program crashes and
incorrect results. This raises the idea of software verification for geometric
algorithms: to guarantee robust implementation that will
complete successfully the tasks for any kind of input.
Finite Precision Approximation converts the
representation of the input into finite-precision. The goal is to
make the representation more robust for algorithms that follow.
I promoted the study of Finite Precision Approximation by
introducing techniques that work on arrangements of line segments in
the plane. In 2002, I published the paper Iterated Snap Rounding with Prof. Halperin in the journal Computational Geometry,
Theory and Applications (CGTA). The
paper presents a different variant for the well known Snap Rounding. This work was further improved in the paper Iterated Snap Rounding with Bounded Drift that was presented in the 22nd Annual ACM Symposium on Computational Geometry
(SoCG) 2006 and received the Best
Theory award in a local conference in Stony Brook in 2005. This work
has been accepted for publication in the journal Computational Geometry,
Theory and Applications (CGTA). My work was further
extended in the Canadian Conference on Computational Geometry (CCCG), 2007 with the paper
Extending the Power of Snap Rounding Variants . Another
Finite-Precision technique is the Controlled Perturbation. I
developed Controlled Perturbation for arrangement of line segments
in the plane which concentrates in ideas for optimizing the
perturbation magnitude. This work was presented in a workshop in
2006 with the title Controlled Perturbation of
Line Segments in 2D with Smart Processing Order
and I plan to submit it for further publication soon.
Art Gallery is one of the most popular studies in Computational Geometry. The problem
is to cover a domain by placing the minimum amount of stationary
sensors that can inspect the entire domain visually. The problem is
well motivated in the field of sensor networking where the goal is to
cover the area with a small set of sensors. Using heuristics that we
developed, we were able to present practical methods for optimizing the sensor
placements efficiently inside polygonal domains (with or without holes), to
cover the entire area. To the best of our knowledge, this is the
first publication of this kind. We developed a software package in
C++, using CGAL libraries. Our many experiments showed very
efficient results, that were usually optimal or very close to
optimal. This work was presented in ALENEX 2007 under the title Locating Guards for Visibility Coverage of
Polygons.
I extended this work to support
dynamic environments in which the sensors translate on predefined routes inside the domain. The
challenge here is to optimize the length of the routes. In this work
the number of sensors is a parameter of the problem; our heuristics
support any number of sensors. This work is closely related to the
area of robot motion planning. To the best of my knowledge, this is
the first theoretical, practical and experimental work done for this important
task. This work was accepted to WEA 2008 under the title Computing Multiple Watchman Routes .
A preliminary version was presented in a Computational Geometry workshop
in 2007. I am also consistently working on finding optimization provable algorithms
to different variants of the above problems.
Reconstructing models from scanned data is a challenging task that
combines techniques from Computational Geometry and Computer
Graphics. Most state-of-the-art techniques assume that the
scanned objects are smooth and produce smooth output. However,
developing techniques to preserve the sharp features are more challenging and very important
for obtaining realistic models. We are currently working on ideas that
combine Computational Geometry and Computer Graphics techniques to provably
reconstruct objects while preserving their sharp features.
Detecting collisions is one of the most challenging
tasks in Computer Graphics as it's inherent complexity is larger than
other common tasks. It is even more challenging when the model
contains objects that deform. My research proficiency exam was
devoted to this subject. I wrote a survey and
developed software that detects collisions in deformable models. This
work was described in depth in the corresponding report. As of
today, we are trying to develop efficient algorithms
to perform fast proximity queries in deformable environments.
7th International Workshop on Experimental Algorithms, WEA, 2008
We present heuristics to compute multiple watchmen routes. Given a polygon (with or without
holes) and a parameter k, we compute a set of k routes inside the polygon such that any point inside
the polygon is visible from at least one point along one route. We measure the quality of our solutions
by either the length of the longest route and the sum of route lengths, where the goal is to minimize
each. We start by computing a set of static guards [2], construct k routes that visit all the static guards
and further shorten the routes while maintaining full coverage of the polygon. We implemented the
algorithm and present extensive results to evaluate our methods, including a comparison with lower
bound routes based on the idea of visiting large number of visibility-independent witness points.
Our experiments showed that for a large suite of input data our heuristics give efficient routes that are
comparable with the optimal solutions.
with
Yoav Amit and J.S.B Mitchell
Workshop on Algorithm Engineering
and Experiments, ALENEX, 2007
A preliminary version appeared in
the 15th Annual Fall Workshop on Computational Geometry and
Visualization, University of Pennsylvania, 2005
We propose heuristics for visibility coverage of a polygon with the fewest point guards. This optimal coverage
problem, often called the art gallery problem, is known
to be NP-hard, so most recent research has focused on
heuristics and approximation methods. We evaluate our
heuristics through experimentation, comparing the upper
bounds on the optimal guard number given by our methods with computed lower bounds based on heuristics for
placing a large number of visibility-independent witness
points. We give experimental evidence that our heuristics perform well in practice, on a large suite of input
data; often the heuristics give a provably optimal result,
while in other cases there is only a small gap between the
computed upper and lower bounds on the optimal guard
number.
To appear in Computational Geometry, Theory and
Application
Preliminaries versions appeared in the Proc. 22nd
Annual ACM Symposium on Computational Geometry, pp. 367-376, 2006
and also in the 15th Annual Fall Workshop on Computational
Geometry and Visualization, University of Pennsylvania, 2005
Best Paper Award,Graduate Research Conference, Stony Brook University, 2005
Snap Rounding and its variant, Iterated Snap Rounding, are methods for converting
arbitrary-precision arrangements of segments into a fixed-precision representation (we call
them SR and ISR for short). Both methods approximate each original segment by a polygonal
chain, and both may lead, for certain inputs, to rounded arrangements with undesirable
properties: in SR the distance between a vertex and a non-incident edge of the rounded
arrangement can be extremely small, inducing potential degeneracies. In ISR, a vertex and
a non-incident edge are well separated, but the approximating chain may drift far away from
the original segment it approximates. We propose a new variant, Iterated Snap Rounding
with Bounded Drift, which overcomes these two shortcomings of the earlier methods. The
new solution augments ISR with simple and efficient procedures that guarantee the quality
of the geometric approximation of the original segments, while still maintaining the property
that a vertex and a non-incident edge in the rounded arrangement are well separated. We
investigate the properties of the new method and compare it with the earlier variants. We
have implemented the new scheme on top of CGAL, the Computational Geometry Algorithms
Library, and report on experimental results.
with Dan Halperin
Computational Geometry: Theory and
Applications, 23:2 (2002), pp.~209--225.
A preliminary version
appeared in the 17th European Workshop on Computational Geometry,
Berlin, 2001, 82-85.
Snap Rounding is a well known method for converting arbitrary-precision
arrangements of segments into a fixed-precision representation. We point out that in
a snap-rounded arrangement, the distance between a vertex and a non-incident edge can
be extremely small compared with the width of a pixel in the grid used for rounding.
We propose and analyze an augmented procedure, Iterated Snap Rounding, which rounds the arrangement
such that each vertex is at least half-the-width-of-a-pixel away from any non-incident edge.
Iterated Snap Rounding preserved the topology of the original arrangement in the same sense that
the original scheme does. However, the guaranteed quality of the approximation degrades.
Thus each scheme may be suitable in different situations. We describe an implementation
of both schemes. In our implementation we substitute an intricate data structure for
segment/pixel intersection that is used to obtain good worst-case resource bounds
for Iterated Snap Rounding by a simple and effective data structure which is a cluster of
kd-trees. Finally, we present rounding examples obtained with the implementation.
Submitted to ESA 2008
A preliminary version appeared in the 16th Fall Workshop on Computational and
Combinatorial Geometry, Smith College, 2006
Controlled Perturbation is a framework for perturbing geometric
input to make it more robust for fixed-precision manipulation.
We present a Controlled Perturbation scheme for sets of line
segments in the plane (CPLS, for short). CPLS perturbs the
endpoints of the line segments to eliminate degeneracies that may
cause errors when using fixed-precision arithmetic. We implemented
CPLS and provide experimental results.
In the core of this work, we present novel techniques to decrease
the perturbation magnitude by determining a smart order for
processing the endpoints. We designed and implemented several
methods for that purpose. Our experiments show that these methods
are effective in decreasing the perturbation magnitude.
with J.S.B Mitchell
Proc. 17th Annual Fall Workshop on Computational Geometry and
Visualization, IBM Watson, 2007
The stabbing number of a geometric structure in the plane with respect
to lines is the maximum number of times any line stabs
(intersects) the structure. We present algorithms for constructing
popular geometric data structures with small stabbing
number and for computing lower bounds on an optimal
solution. We evaluate our methods experimentally.
19th Canadian Conference on Computational Geometry, 2007.
Snap Rounding (SR for short) is a method for convert-
ing arbitrary-precision arrangements of line segments
into a fixed-precision representation. In the previ-
ous years two variants of SR were presented: Iterated
Snap Rounding (ISR) and Iterated Snap Rounding with
Bounded Drift (ISRBD). Their goal was to eliminate an
undesirable property that SR possesses. Prior to their
appearances, the capabilities of SR were extended in
two publications. One showed how to support dynamic
rounding (insertion and deletion of line segments). The
other extended SR to 3D (limited to arrangement of line
segments). In this work we show how to extend ISR and
ISRBD to support these capabilities.
In CGAL Manual, Chapter 22, P.1617-1628
with Michael Hoffmann
In CGAL Manual, Chapter 49, P.2763-2781
Miscellaneous
Preliminary Report, Stony Brook University, 2006
In this report, I provide an extensive survey of the research I am
pursuing in my PhD studies. It mainly includes both results that
have been obtained so far and detailed plans for the future.
Research Project Report, Stony Brook University, 2005
We survey the work that have been done in collision detection in general and in
collision detection of deformable models in particular.
We describe our current status,
the application we developed and our future plans.
Technical Report, Stony Brook University, 2007
We study the problem of optimizing the spanning tree of a
set of points in 3D, whose projection onto a given plane contains
no crossing edges. We prove that this problem is NPcomplete
and show that greedy algorithms (similar to Prim or
Kruskal), which would be natural heuristics to approximate
this problem, can perform arbitrarily bad.
Technical Report, Tel Aviv University, 2001
