Cuttings for Disks and Axis-Aligned Rectangles in Three-Space ∗ (2009)
Eynat Rafalin, Diane L. Souvaine, Csaba D. Tóth
We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r ∈ N, an 1 r-cutting is a covering of the...
Cuttings for Disks and Axis-Aligned Rectangles in Three-Space ∗ (2009)
Eynat Rafalin, Csaba D. Tóth, Diane L. Souvaine
We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r ∈ N, an 1 r-cutting is a covering of the...
Erratum for “Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs” (2009)
Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóth
A set of n disjoint line segments in the plane and a permutation π of the 2n segment endpoints define a partition of the plane into convex faces: extend the segments beyond their endpoints...
Abstract Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs (2009)
Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóth
The empty space around n disjoint line segments in the plane can be partitioned into n + 1 convex faces by extending the segments in some order. The dual graph of such a partition is the plane graph...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues (2008)
Eynat Rafalin, Robert T. Schweller, Diane L. Souvaine
We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
The field of ethnomathematics is the study of mathematics in the works of art of various cultures [2, 3, 9, 13]. The concepts
Describing Multivariate Distributions with Nonlinear Variation Using Data Depth 1 (2008)
Rima Izem, Eynat Rafalin, Diane L. Souvaine
Growth curves of plants and animals, human speech, gene expression signals, and medical images or 3-dimensional shapes of cancer tumors, are all real life examples of high dimensional multivariate...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues (2008)
Eynat Rafalin, Robert T. Schweller, Diane L. Souvaine
We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various...
Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues (2008)
Eynat Rafalin, Robert T. Schweller, Diane L. Souvaine
We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
Abstract Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs (2008)
Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóth
The empty space around n disjoint line segments in the plane can be partitioned into n + 1 convex faces by extending the segments in some order. The dual graph of such a partition is the plane graph...
Combinatorial Complexity of Signed Discs (2007)
Diane L. Souvaine, Chee-keng Yap
Let C + and C \Gamma be two collections of topological discs of arbitrary radii. The collection of discs is `topological' in the sense that their boundaries are Jordan curves and each pair of...
Tight bounds for connecting sites across barrieres (2006)
David W. Krumme, Diane L. Souvaine, Eynat Rafalin, Csaba D. Tóth
Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight-line minimum cost spanning tree on the sites, where the cost is proportional to the number...
Hinged dissection of polypolyhedra (2005)
Erik D. Demaine, Martin L. Demaine, Jeffrey F. Lindy, Diane L. Souvaine
Fig. 1. Hinged dissection ofsquare and equilateral triangle [8]. Different shades showdifferent folded states.
Hinged dissection of polypolyhedra (2005)
Erik D. Demaine, Martin L. Demaine, Jeffrey F. Lindy, Diane L. Souvaine
Abstract. This paper presents a general family of 3D hinged dissections for polypolyhedra, i.e., connected 3D solids formed by joining several rigid copies of the same polyhedron along identical...
Automating Software Documentation (1998)
Karen Paffendorf, Diane L. Souvaine
This paper describes automating the documentation of a software control structure. The code is preprocessed to take the form of directed graphs. The following tools are used for drawing the directed...
Constructing Piecewise Linear Homeomorphisms (1997)
By Diane Souvaine, Diane L. Souvaine, Rephael Wenger
Let P = fp 1 ; : : : ; p n g and Q = fq 1 ; : : : ; q n g be two point sets lying in the interior of rectangles in the plane. We show how to construct a piecewise linear homeomorphism of size O(n 2 )...
A Tight Bound for Edge Guards in Monotone Polygons (1992)
Iliana Bjorling-sachs, Diane L. Souvaine
Supported by DIMACS research assistantship 2 Permanent Member of DIMACS 3
On Solving Geometric Optimization Problems Using Shortest Paths (1990)
Elefterios A. Melissaratos, Diane L. Souvaine
We have developed techniques which contribute to efficient algorithms for certain geometric optimiza-tion problems involving simple polygons: computing minimum separators, maximum inscribed triangles,
Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions
Elefterios A. Melissaratos, Diane L. Souvaine
The goal of this paper is to show that the concept of the shortest path inside a polygonal region contributes to the design of efficient algorithms for certain geometric optimization problems...