On Convex Decompositions of Points (2008)
Kiyoshi Hosono, David Rappaport, Masatsugu Urabe
Given a planar point set in general position, S, we seek a partition of the points into convex cells, such that the union of the cells forms a simple polygon, P , and every point from S is on the...
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...
Compatible Geometric Matchings (2007)
Aichholzer, Oswin, Bereg, Sergey, Dumitrescu, Adrian, García, Alfredo, Huemer, Clemens, Hurtado, Ferran, ...
This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{compatible} if they have the same vertex set and their union is also non-crossing. Our first result...
The Distance Geometry of Music (2007)
Demaine, Erik D., Gomez-Martin, Francisco, Meijer, Henk, Rappaport, David, Taslakian, Perouz, Toussaint, Godfried T., ...
We demonstrate relationships between the classic Euclidean algorithm and many other fields of study, particularly in the context of music and distance geometry. Specifically, we show how the...
Biclique Edge Cover Graphs and Confluent Drawings (2007)
Hirsch, Michael, Meijer, Henk, Rappaport, David
Confluent drawing is a technique that allows some non-planar graphs to be visualized in a planar way. This approach merges edges together, drawing groups of them as single tracks, similar to train...
Biclique Edge Cover Graphs and Confluent Drawings (2007)
Hirsch, Michael, Meijer, Henk, Rappaport, David
Confluent drawing is a technique that allows some non-planar graphs to be visualized in a planar way. This approach merges edges together, drawing groups of them as single tracks, similar to train...
Algorithms for Computing Geometric Measures of Melodic Similarity (2006)
Aloupis, Greg., Fevens, Thomas., Langerman, Stefan., Mesa, Antonio., Nunez, Yurai., ...
Computer Music Journal - Volume 30, Number 3, Fall 2006
(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram (2006)
Funke, Stefan, Malamatos, Theocharis, Matijevic, Domagoj, Wolpert, Nicola, Rappaport, David
For a given point set in Euclidean space we consider the problem of finding (approximate) nearest neighbors of a query point but restricting only to points that lie within a fixed cone with apex at...
El Compás Flamenco: A Phylogenetic Analysis (2004)
J. Miguel, Francisco Gomez, David Rappaport, Díaz-báñez Giovanna, Giovanna Farigu, ...
The flamenco music of Andalucia in Southern Spain is characterized by hand clapping patterns in which the underlying meter is manifested through accented claps. A phylogenetic analysis of the five...
Computing a Geometric Measure of the Similarity between two Melodies (2003)
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nunez, ...
Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle . We wish to rigidly move one chain so that the total area between the two chains is minimized....
On the Visibility Graph of Convex Translates (2000)
Kiyoshi Hosono, Henk Meijer, David Rappaport
We show that the visibility graph of a set of non-intersecting translates of the same compact convex object in IR always contains a Hamiltonian path. Furthermore, we show that every other edge in the...
Minimum Convex K-Partitions of a Linearly Constrained Point Set (1999)
Thomas Fevens, Henk Meijer, David Rappaport
We present an optimization algorithm to determine a partition of the convex hull of a finite set of ponts in the plane. The partition uses the points as corners of convex polygonal cells, each cell...
Algorithms for Cluster Busting in Anchored Graph Drawing (1998)
Kelly A. Lyons, Henk Meijer, David Rappaport
Given a graph G and a drawing or layout of G, it is sometimes desirable to alter or adjust the layout. The challenging aspect of designing layout adjustment algorithms is to maintain a user's...
Minimum Convex Partition of a Constrained Point Set (1998)
Thomas Fevens, Henk Meijer, David Rappaport
: A convex partition with respect to a point set S is a planar subdivision whose vertices are the points of S, where the boundary of the unbounded outer face is the boundary of the convex hull of S,...
Minimum Weight Convex Quadrangulation of a Constrained Point Set (1997)
Thomas Fevens, Henk Meijer, David Rappaport
Summary: A convex quadrangulation with respect to a point set S is a planar subdivision whose vertices are the points of S, where the boundary of the unbounded outer face is the boundary of the...
Minimum Weight Convex Quadrangulation of a Constrained Point Set (1997)
Thomas Fevens, Henk Meijer, David Rappaport
A convex quadrangulation with respect to a point set S is a planar subdivision whose vertices are the points of S, where the boundary of the unbounded outer face is the boundary of the convex hull of...
Minimum Weight Convex Quadrangulation of a Constrained Point Set (1997)
Thomas Fevens, Henk Meijer, David Rappaport
1 Introduction There are many problems for which it is necessary to find a numerical solution of a complicated system of differential equations. To find such a numerical solution, the finite element...
Dominance Drawings of Bipartite Graphs (1994)
Peter Eades, Hossam ElGindy, Michael Houle, Bill Lenhart, Mirka Miller, David Rappaport, ...
Let G = (S; T; E) denote a directed bipartite graph with S a set of sources and T a set of sinks. Using vectors s = (s1 ; s2 ; :::s k) and t = (t1 ; t2 ; :::t k) in R k to represent the elements s 2...
Probing a Set of Hyperplanes by Lines and Related Problems (1993)
Yasukazu Aoki, Hiroshi Imai, Keiko Imai, David Rappaport
Suppose that for a set H of n unknown hyperplanes in the Euclidean d-dimensional space, a line probe is available which reports the set of intersection points of a query line with the hyperplanes....
Computing Simple Circuits from a Set of Line Segments (1990)
David Rappaport, Hiroshi Imai, Godfried T. Toussaint
We address the problem of connecting line segments to form the boundary of a simple polygon --- a simple circuit. However, not every set of segments can be so connected. We present an O(n log n)-time...