Optimal covering tours with turn costs (2009)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, S Ándor, P. Fekete, ...
Abstract. We give the first algorithmic study of a class of “covering tour ” problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps out...
Maximum Thick Paths in Static and Dynamic Environments ABSTRACT (2009)
We consider the problem of finding a maximum number of disjoint paths for unit disks moving amidst static or dynamic obstacles. For the static case we give efficient exact algorithms, based on...
Abstract Hamiltonian Cycles in Triangular Grids (2009)
Valentin Polishchuk, Esther M. Arkin
We study the Hamiltonian Cycle problem in graphs induced by subsets of the vertices of the tiling of the plane with equilateral triangles. By analogy with grid graphs we call such graphs triangular...
On Geometric Stable Roommates and Minimum-Weight Matching Robustness (Extended Abstract) ∗ (2008)
Valentin Polishchuk, Esther M. Arkin, Kobus Barnard, Kevin Coogan, Alon Efrat, ...
Abstract This paper consists of two parts, both of which address stability of perfect matchings. In the first part we consider instances of the Stable Roommates problem that arise from geometric...
ABSTRACT Minimum-Cost Coverage of Point Sets by Disks ∗ (2008)
Helmut Alt, Jeff Erickson, Jonathan Lenchner, Esther M. Arkin, Sándor P. Fekete
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t j) and radii (r j) that cover a given set of demand points Y...
ABSTRACT Improved Approximation Algorithms for the Freeze-Tag Problem (2008)
Esther M. Arkin, Simai He, Michael A. Bender, Dongdong Ge
In the Freeze-Tag Problem, the objective is to awaken a set of “asleep ” robots, starting with only one “awake ” robot. A robot awakens a sleeping robot by moving to the sleeping robot’s...
Esther M. Arkin, Martin Held, Steven S. Skiena
High-performance rendering engines in computer graphics are often pipelined, and their speed is bounded by the rate at which triangulation data can be sent into the machine. To reduce the data rate,...
Esther M. Arkin, Gill Barequet
Algorithms for Two-Box Covering We study the problem of covering a set of points or polyhedra in ℜ 3 with two axis-aligned boxes in order to minimize a function of the measures of the two boxes,...
On Minimum-Area Hulls (Extended Abstract) (2008)
Esther M. Arkin, Yi-jen Chiang, Martin Held, Steven S. Skiena, Tae-cheon Yang
Abstract. We study some minimum-area hull problems that generalize the notion of convex hull to star-shaped and monotone hulls. Specifically, we consider the minimum-area star-shaped hull problem:...
Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Martin Skutella
Abstract. An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of “asleep ” robots, by having an awakened robot move...
Matching points with squares (2008)
Bernardo M. Ábrego, Esther M. Arkin, Silvia Fernández-merchant, Ferran Hurtado, Mikio Kano, ...
Given a class C of geometric objects and a point set P, a C-matching of P is a set M = {C1,...,Ck} ⊆ C of elements of C such that each Ci contains exactly two elements of P and each element of P...
Esther M. Arkin, Refael Hassin
Given a collection of sets of cardinality at most k, with weights for each set, the maximum weighted packing problem is that of finding a collection of disjoint sets of maximum total weight. We study...
Esther M. Arkin, Refael Hassin
The tree and tour cover problems on an edge-weighted graph are to compute a minimum weight tree and closed walk, respectively, whose vertices form a vertex cover. Both problems are NP-hard. In this...
Esther M. Arkin, Henk Meijer, David Rappaport, Steven S. Skiena
A fundamental problem in model-based computer vision is that of identifying which of a given set of geometric models is present in an image. Considering a "probe " to be an oracle...
Esther M. Arkin, Giri Narasimhan
We study a variety of geometric network optimization problems on a set of points, in which we are given a resource bound, B, on the total length of the network, and our objective is to maximize the...
Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristan, ...
We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity (S) of S is given by the smallest number of reflex vertices...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia
S. Skiena y The easiest way to refold a road map is differently.--- Jones's Rule of the Road (M. Gardner [3]) 1
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristan, ...
We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity (S) of S is given by the smallest number of reflex vertices...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Saurabh Sethia
We give the first algorithmic study of a class of "covering tour " problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Saurabh Sethia
We give the rst algorithmic study of a class of \covering tour " problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps out a...
Esther M. Arkin, Martin Held, Vera Sacristan, Steven S. Skiena, Tae-cheon Yang
yy We study some minimum-area hull problems that generalize the notion of convex hull to star-shaped and monotone hulls. Specifically, we consider the minimum-area star-shaped hull problem: Given an...
When Can You Fold a Map? (2007)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
A Note on Orientations of Mixed Graphs (2007)
Esther Arkin Refael, Esther M. Arkin, Refael Hassin
We consider orientation problems on mixed graphs in which the goal is to obtain a directed graph satisfying certain connectivity requirements.
When Can You Fold a Map? (2007)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Online Dispersion Algorithms for Swarms of Robots (2007)
Tien-ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sándor P. Fekete
We illustrate algorithms for dispersing a swarm of primitive robots in a two-dimensional unknown environment R. Each robot in the swarm is equipped with a very simple sensor that is able to query the...
When Can You Fold a Map? (2007)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a at folding by a sequence of simple folds?...
Valentin Polishchuk, Esther M. Arkin, Kobus Barnard, Kevin Coogan, Alon Efrat, ...
We introduce the notion of robustness of the minimum-weight perfect matching. The robustness measures how much the edge weights of a graph are allowed to change before the minimum-weight matching...
Geometric Stable Roommates (2007)
Esther M. Arkin, Alon Efrat, Valentin Polishchuk
We consider instances of the Stable Roommates problem that arise from geometric representation of participants preferences: a participant is a point in a metric space, and his preference list is...
Minimum-Cost Coverage of Point Sets by Disks (2006)
Arkin, Esther M., Broennimann, Herve, Erickson, Jeff, Fekete, Sandor P., Knauer, Christian, Lenchner, Jonathan, ...
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t_j) and radii (r_j) that cover a given set of demand points Y...
Arkin, Esther M., Bender, Michael A., Mitchell, Joseph S. B., Polishchuk, Valentin
We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a...
Esther M. Arkin, Michael A. Bender
Abstract: We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to...
Minimum-cost coverage of point sets by disks (2006)
Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, ...
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t j) and radii (r j) that cover a given set of demand points Y...
Esther M. Arkin, Michael A. Bender
Abstract: We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to...
Esther M. Arkin, Michael A. Bender
Abstract: We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to...
The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (2004)
Arkin, Esther M., Bender, Michael A., Fekete, Sandor P., Mitchell, Joseph S. B., Skutella, Martin
An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of ``asleep'' robots, by having an awakened robot move to their...
Esther M. Arkin, Alper Yildirim
E-Mail: piyush at acm dot org The thesis source is covered under the GNU General Public License. The thesis source comes with ABSOLUTELY NO WARRANTY; without even the implied warranty of...
Optimal Covering Tours with Turn Costs (2003)
Arkin, Esther M., Bender, Michael A., Demaine, Erik D., Fekete, Sandor P., Mitchell, Joseph S. B., Sethia, Saurabh
We give the first algorithmic study of a class of ``covering tour'' problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps out a specified...
Improved approximation algorithms for the freeze-tag problem (2003)
Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai Hejoseph, S. B. Mitchell
Abstract The following scheduling problem naturally arises in thestudy of swarm robotics. Consider a set of n robots, mod-eled as points in some metric space (e.g., vertices of an edge-weighted...
On the reflexivity of point sets (2003)
Esther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristán, ...
We introduce a new measure for planar point sets S that captures a combinatorial distance that S is from being a convex set: The reflexivity ρ(S) ofS is given by the smallest number of reflex...
On the reflexivity of point sets (2003)
S Andor, P. Fekete, Esther M. Arkin, Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado, ...
x We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity (S) of S is given by the smallest number of reflex...
Online Dispersion Algorithms for Swarms of Robots (2003)
Tien-ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sandor Fekete
INTRODUCTION We illustrate algorithms for dispersing a swarm of primitive robots in a two-dimensional unknown environment R. Each robot in the swarm is equipped with a simple sensor that is able to...
An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures (2003)
Esther M. Arkin, Sándor P. Fekete, Or P. Fekete
We study algorithmic aspects of bending wires and sheet metal into a specified structure. Problems of this type are closely related to the question of deciding whether a simple non-self-intersecting...
On the reflexivity of point sets (2003)
Esther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristán, ...
Abstract. We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity ρ(S) ofS is given by the smallest number of...
Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments (2002)
Hsiang, Tien-Ruey, Arkin, Esther M., Bender, Michael, Fekete, Sandor P., Mitchell, Joseph S. B.
We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire...
The Lazy Bureaucrat Scheduling Problem (2002)
Arkin, Esther M., Bender, Michael A., Mitchell, Joseph S. B., Skiena, Steven S.
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single ``machine'') who performs the tasks. A typical worker's objective is to minimize the...
On the Reflexivity of Point Sets (2002)
Arkin, Esther M., Fekete, Sandor P., Hurtado, Ferran, Mitchell, Joseph S. B., Noy, Marc, Sacristan, Vera, ...
We introduce a new measure for planar point sets S that captures a combinatorial distance that S is from being a convex set: The reflexivity rho(S) of S is given by the smallest number of reflex...
An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures (2002)
Arkin, Esther M., Fekete, Sandor P., Mitchell, Joseph S. B.
We study algorithmic aspects of bending wires and sheet metal into a specified structure. Problems of this type are closely related to the question of deciding whether a simple non-self-intersecting...
Analysis of heuristics for the Freeze-Tag Problem (2002)
Marcelo O. Sztainberg, Esther M. Arkin, Michael A. Bender
In the Freeze Tag Problem (FTP) we are given a swarm of n asleep (frozen or inactive) robots and a single awake (active) robot, and we want to awaken all robots in the shortest possible time. A robot...
The freeze-tag problem: How to wake up a swarm of robots (2002)
Esther M. Arkin, Michael A. Bender, Sandor P. Fekete, Martin Skutella
An optimization problem that naturally arises in the study of "swarm robotics " is to wake up a set of "asleep " robots, starting with only one "awake...
The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (2002)
Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Martin Skutella
An optimization problem that naturally arises in the study of "swarm robotics" is to wake up a set of "asleep" robots, starting with only one "awake" robot. One robot...
The Lazy Bureaucrat Scheduling Problem (2002)
Esther M. Arkin, Michael A. Bender, Steven S. Skiena
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single \machine") who performs the tasks. A typical worker's objective is to minimize...
Vitus J. Leung, Cynthia A. Phillips, Jeanette R. Johnston, Esther M. Arkin, Michael A. Bender, ...
The Computational Plant or Cplant is a commodity-based supercomputer under development at Sandia National Laboratories. This paper describes resource-allocation strategies to achieve processor...
Analysis of Heuristics for the Freeze-Tag Problem (2002)
Marcelo O. Sztainberg, Esther M. Arkin, Michael A. Bender
In the Freeze Tag Problem (FTP) we are given a swarm of n asleep (frozen or inactive) robots and a single awake (active) robot, and we want to awaken all robots in the shortest possible time. A robot...
Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments (2002)
Tien-ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sandor P. Fekete
We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire...
When can you fold a map (2001)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
Abstract. We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple...
Succinct Strip Encoding of Triangle Meshes (2001)
Michael A. Bender, Outside Member, Esther M. Arkin, Xinyu Xiang, Xinyu Xiang, ...
OF THE DISSERTATION 2001 A fundamental algorithmic problem in computer graphics is that of computing a succinct encoding of a triangulation of a polygonal surface model in order to be able to...
Optimal covering tours with turn costs (2001)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, S Ándor, P. Fekete, ...
Abstract. We give the first algorithmic study of a class of “covering tour ” problems related to the geometric traveling salesman problem: Find a polygonal tour for a cutter so that it sweeps out...
Some lower bounds on geometric separability problems (2001)
Esther M. Arkin, Ferran Hurtado, Carlos Seara, Steven S. Skiena
We obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. In particular, we show Ω(n log n) time lower bounds for separability by...
Increasing Digraph Arc-Connectivity by Arc Addition, Reversal and Complement (2001)
Esther M. Arkin, Refael Hassin, Shimon Shahar
This paper deals with increasing the arc-connectivity of directed graphs by arc additions, reversals or complements. We study several optimization problems, which dier in their arcconnectivity...
Succinct Strip Encoding of Triangle Meshes BY (2001)
Xinyu Xiang, Xinyu Xiang, Michael A. Bender, Outside Member, Esther M. Arkin, ...
We, the dissertation committe for the above candidate for the Doctor of Philosophy degree, hereby recommend acceptance of this dissertation.
Some lower bounds on geometric separability problems (2001)
Esther M. Arkin, Ferran Hurtado, Carlos Seara, Steven S. Skiena
In this paper we obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. More precisely, we show Ω(n log n) time lower bounds for the...
When Can You Fold a Map? (2000)
Arkin, Esther M., Bender, Michael A., Demaine, Erik D., Demaine, Martin L., Mitchell, Joseph S. B., Sethia, Saurabh, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Approximating the Maximum Quadratic Assignment Problem (2000)
Esther M. Arkin, Refael Hassin, Maxim Sviridenko
this paper appeared in Proc. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), 889-890, January, 2000.
On the manufacturability of paperclips and sheet metal structures (1999)
Esther M. Arkin, Sandor P. Fekete, Steven S. Skiena
We consider an algorithmic problem that arises in the study of the manufacturability of sheet metal parts: Given a flat piece, F, of sheet metal (or cardboard, or other bendable "stiff...
The Lazy Bureaucrat Scheduling Problem (1999)
Esther M. Arkin, Michael A. Bender, Steven S. Skiena
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single \machine") who performs the tasks. The worker's objective may be to minimize the...
The Lazy Bureaucrat Scheduling Problem (1999)
Esther M. Arkin, Michael A. Bender, Steven S. Skiena
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single "machine") who performs the tasks. The worker's objective may be to...
An Efficiently Computable Metric for Comparing Polygonal Shapes. (1998)
Arkin, Esther M., Chew, L. P., Huttenlocher, Daniel P., Kedem, Klara, Mitchell, Joseph S.
Model-based recognition is concerned with comparing a shape A, which is stored as a model for some particular object, with a shape B, which is found to exist in an image. If A and B are close to...
An Efficiently Computable Metric for Comparing Polygonal Shapes, (1998)
Arkin, Esther M., Chew, L. P., Huttenlocher, Daniel P., Kedem, Klara, Mitchell, Joseph S.
Graph partitions with minimum degree constraints, Discrete Mathematics 190 (1998)
Esther M. Arkin, Refael Hassin
Given a graph with n nodes and minimum degree ffi, we give a polynomial time algorithm that constructs a partition of the nodes of the graph into two sets X and Y such that the sum of the minimum...
Probe Trees for Touching Character Recognition (1998)
George N. Sazaklis, Esther M. Arkin, Steven S. Skiena
The problem of touching characters is very important for the recognition of low quality text. A solution is presented here for the problem of touching character recognition for fixed font, using a...
Efficient Collision Detection For Interactive 3D Graphics And Virtual Environments (1998)
Esther M. Arkin, Amitabh Varshney, James Thomas Klosowski, James Thomas Klosowski, James Thomas Klosowski
of the Dissertation Efficient Collision Detection for Interactive 3D Graphics and Virtual Environments by James Thomas Klosowski Doctor of Philosophy in Applied Mathematics and Statistics State...
Restricted delivery problems on a network," Networks (1997)
Esther M. Arkin, Refael Hassin, Limor Klein
We consider a delivery problem on a network one is given a network in which nodes have supplies or demands for certain products, and arcs have lengths satisfying the Triangle Inequality. A vehicle of...
Minimum diameter covering problems (1997)
Esther M. Arkin, Refael Hassin
Abstract A set V and a collection of (possibly non-disjoint) subsets are given. Also given is a real matrix describing distances between elements of V. A cover is a subset of V containing at least...
Approximation Algorithms for Lawn Mowing and Milling (1997)
Esther M. Arkin, Esther M. Arkin, Sandor P. Fekete, Sandor P. Fekete, ...
We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a "cutter" (typically,...
Approximation Algorithms for Lawn Mowing and Milling (1997)
Esther M. Arkin, Esther M. Arkin, Sandor P. Fekete, Sandor P. Fekete, ...
We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a "cutter" (typically,...
On the Maximum Scatter TSP (1997)
Esther M. Arkin, Yi-Jen Chiang, Steven S. Skiena, Tae-Cheon Yang
. We study the problem of computing a Hamiltonian tour (cycle) or path on a set of points in order to maximize the minimum edge length in the tour or path. This "maximum scatter" TSP is...
Resource-Constrained Geometric Network Optimization (Extended abstract) (1997)
Esther M. Arkin, Giri Narasimhan
We study a variety of geometric network optimization problems on a set of points, in which we are given a resource bound, B, on the total length of the network, and our objective is to maximize the...
Approximation Algorithms for Lawn Mowing and Milling (1997)
Esther M. Arkin, Esther M. Arkin, Esther M. Arkin, Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete, ...
We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a "cutter" (typically,...
On the Maximum Scatter TSP (Extended Abstract) (1997)
E. M. Arkin, Yi-Jen Chiang, Esther M. Arkin, Steven S. Skiena, Tae-cheon Yang
) Esther M. Arkin y Yi-Jen Chiang z Joseph S. B. Mitchell x Steven S. Skiena -- Tae-Cheon Yang k To appear in Proc. ACM-SIAM Symposium on Discrete Algorithms (1997) Abstract We study the problem of...
On the Maximum Scatter TSP (1996)
Esther M. Arkin, Yi-Jen Chiang, Steven S. Skiena, Tae-cheon Yang
We study the problem of computing a Hamiltonian tour (cycle) or path on a set of points in order to maximize the minimum edge length in the tour or path. This "maximum scatter" TSP is...
Optimization problems related to zigzag pocket machining (1996)
Esther M. Arkin, Martin Held, Christopher L. Smith
(2) z
Approximating The Tree And Tour Covers Of A Graph (1996)
Esther M. Arkin, Magnús M. Halldórsson, Refael Hassin
The tree and tour cover problems on an edge-weighted graph are to compute a minimum weight tree and closed walk, respectively, whose vertices form a vertex cover. Both problems are NP-hard. In this...
Approximation algorithms for the geometric covering salesman problem (1994)
Esther M. Arkin, Refael Hassin
We introduce a geometric version of the Covering Salesman Problem: Each of the n salesman's clients specifies a neighborhood in which they are willing to meet the salesman. Identifying a tour of...
Hamiltonian Triangulations for Fast Rendering (1994)
Esther M. Arkin, Martin Held, Steven S. Skiena
High-performance rendering engines in computer graphics are often pipelined, and their speed is bounded by the rate at which triangulation data can be sent into the machine. To reduce the data rate,...
Arrangements of Segments that Share Endpoints: Single Face Results (1994)
Esther M. Arkin, Dan Halperin, Klara Kedem, Nir Naor
We provide new combinatorial bounds on the complexity of a face in an arrangement of segments in the plane. In particular, we show that the complexity of a single face in an arrangement of n line...
Hamiltonian Triangulations for Fast Rendering (1994)
Esther M. Arkin, Martin Held, Steven S. Skiena
High-performance rendering engines in computer graphics are often pipelined, and their speed is bounded by the rate at which triangulation data can be sent into the machine. To reduce the data rate,...
Point Probe Decision Trees for Geometric Concept Classes (1993)
Esther M. Arkin, Michael T. Goodrich, David Mount, Christine Piatko, Steven S. Skiena
A fundamental problem in model-based computer vision is that of identifying to which of a given set of concept classes of geometric models an observed model belongs. Considering a "probe"...
Matching points into pairwise-disjoint noise regions: Combinatorial bounds and algorithms (1992)
Esther M. Arkin, Esther M. Arkin, Klara Kedem, Klara Kedem, ...
Please address correspondence to Professor Arkin. 1 We consider several cases of the point matching problem in which we are to find a transformation of a set of n points such that each transformed...
Matching Points into Pairwise-Disjoint Noise Regions: (1992)
Combinatorial Bounds And, Esther M. Arkin, Esther M. Arkin, Klara Kedem, Klara Kedem, ...
We consider several cases of the point matching problem in which we are to find a transformation of a set of n points such that each transformed point lies in one of n given pairwise-disjoint...
Arrangements of Segments that Share Endpoints: Single Face Results (1991)
Esther M. Arkin, Dan Halperin, Klara Kedem
(1) z
Proceedings of the Eighth Annual Symposium on Computational Geometry, pages 102{ (1989)
Helmut Alt, Bernd Behrends, Helmut Alt, Michael Godau, Measuring In, Esther M. Arkin, ...
S. B. Mitchell. An e ciently computable metric for comparing polygonal shapes. In
Complexity of cycle and path problems in graphs /--by Esther M. Arkin. (1986)
Thesis (Ph. D.)--Stanford University, 1986.
Approximating the Maximum Quadratic Assignment Problem
Esther M. Arkin, Refael Hassin, Maxim Sviridenko
this paper will appear, in Proc. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), January, 2000.
Approximating the Maximum Quadratic Assignment Problem
Esther M. Arkin, Refael Hassin
Introduction In the maximum quadratic assignment problem two n \Theta n nonnegative symmetric matrices A = (a ij ) and B = (b ij ) are given and the objective is to compute a permutation of V = f1; :...
Improved Approximation Algorithms for the Freeze-Tag Problem
Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai He
In the Freeze-Tag Problem, the objective is to awaken a set of \asleep" robots, starting with only one \awake" robot. A robot awakens a sleeping robot by moving to the sleeping robot's...