Jean-Daniel Boissonnat

SODA Conference 2017 Conference Paper

An Efficient Representation for Filtrations of Simplicial Complexes

• Jean-Daniel Boissonnat
• Karthik C. S. 0001

MFCS Conference 2017 Conference Paper

Kernelization of the Subset General Position Problem in Geometry

• Jean-Daniel Boissonnat
• Kunal Dutta
• Arijit Ghosh
• Sudeshna Kolay

In this paper, we consider variants of the Geometric Subset General Position problem. In defining this problem, a geometric subsystem is specified, like a subsystem of lines, hyperplanes or spheres. The input of the problem is a set of n points in \mathbb{R}^d and a positive integer k. The objective is to find a subset of at least k input points such that this subset is in general position with respect to the specified subsystem. For example, a set of points is in general position with respect to a subsystem of hyperplanes in \mathbb{R}^d if no d+1 points lie on the same hyperplane. In this paper, we study the Hyperplane Subset General Position problem under two parameterizations. When parameterized by k then we exhibit a polynomial kernelization for the problem. When parameterized by h=n-k, or the dual parameter, then we exhibit polynomial kernels which are also tight, under standard complexity theoretic assumptions. We can also exhibit similar kernelization results for d-Polynomial Subset General Position, where a vector space of polynomials of degree at most d are specified as the underlying subsystem such that the size of the basis for this vector space is b. The objective is to find a set of at least k input points, or in the dual delete at most h = n-k points, such that no b+1 points lie on the same polynomial. Notice that this is a generalization of many well-studied geometric variants of the Set Cover problem, such as Circle Subset General Position. We also study general projective variants of these problems. These problems are also related to other geometric problems like Subset Delaunay Triangulation problem.

TCS Journal 2016 Journal Article

On the complexity of the representation of simplicial complexes by trees

• Jean-Daniel Boissonnat
• Dorian Mazauric

In this paper, we investigate the problem of the representation of simplicial complexes by trees. We introduce and analyze local and global tree representations. We prove that the global tree representation is more efficient in terms of time complexity for searching a given simplex and we show that the local tree representation is more efficient in terms of size of the structure. The simplicial complexes are modeled by hypergraphs. We then prove that the associated combinatorial optimization problems are very difficult to solve and to approximate even if the set of maximal simplices induces a planar graph of maximum degree at most three or a bounded degree hypergraph. However, we prove polynomial time algorithms that compute constant factor approximations and optimal solutions for some classes of instances.

TCS Journal 2008 Journal Article

Anisotropic diagrams: Labelle Shewchuk approach revisited

• Jean-Daniel Boissonnat
• Camille Wormser
• Mariette Yvinec

F. Labelle and J. Shewchuk have proposed a discrete definition of anisotropic Voronoi diagrams. These diagrams are parametrized by a metric field. Under mild hypotheses on the metric field, such Voronoi diagrams can be refined so that their dual is a triangulation, with elements shaped according to the specified anisotropic metric field. We propose an alternative view of the construction of these diagrams, and a variant of Labelle and Shewchuk’s meshing algorithm. This variant computes the Voronoi vertices, using a higher dimensional power diagram and refines the diagram as long as dual triangles overlap. We see this variant as a first step toward a 3-dimensional anisotropic meshing algorithm.

SODA Conference 2007 Conference Paper

On Bregman Voronoi diagrams

• Frank Nielsen
• Jean-Daniel Boissonnat
• Richard Nock

STOC Conference 2004 Conference Paper

Isotopic implicit surface meshing

• Jean-Daniel Boissonnat
• David Cohen-Steiner
• Gert Vegter

SODA Conference 2003 Conference Paper

On the combinatorial complexity of euclidean Voronoi cells and convex hulls of d-dimensional spheres

• Jean-Daniel Boissonnat
• Menelaos I. Karavelas

SODA Conference 1995 Conference Paper

Circular Separability of Polygon

• Jean-Daniel Boissonnat
• Jurek Czyzowicz
• Olivier Devillers
• Mariette Yvinec

ICRA Conference 1994 Conference Paper

From Spider Robots to Half Disk Robots

• Jean-Daniel Boissonnat
• Olivier Devillers
• Sylvain Lazard

Studies the problem of computing the set F of accessible and stable placements of a spider robot. The body of this robot is a single point and the legs are line segments attached to the body. The robot can only put its feet on some regions, called the foothold regions. Moreover, the robot is subject to two constraints: each leg has a maximal extension R (accessibility constraint) and the body of the robot must lie above the convex hull of its feet (stability constraint). The authors present an efficient algorithm to compute F. If the foothold regions are polygons with n edges in total, the authors' algorithm computes F in O(n/sup 2/ log n) time and O(n/sup 2//spl alpha/(n)) space where /spl alpha/ is the inverse of Ackerman's function. /spl Omega/(n/sup 2/) is a lower bound for the size of F. >

ICRA Conference 1994 Conference Paper

Shortest Path Synthesis for Dubins Non-Holonomic Robot

• Xuân-Nam Bui
• Philippe Souères
• Jean-Daniel Boissonnat
• Jean-Paul Laumond

We calculate the partition of the configuration space R/sup 2//spl times/S/sup 1/ of a car-like robot, only moving forwards, with respect to the type of the length optimal paths. This kind of robot is subject to kinematic constraints on its path curvature and its orientation. Starting from the results on shortest paths, we give new optimality conditions on these paths, and compute the partition for any horizontal plane of the configuration space. >

TCS Journal 1993 Journal Article

On the randomized construction of the Delaunay tree

• Jean-Daniel Boissonnat
• Monique Teillaud

The Delaunay tree is a hierarchical data structure which is defined from the Delaunay triangulation and, roughly speaking, represents a triangulation as a hierarchy of balls. It allows a smidynamic construction of the Delaunay triangulation of a finite set of n points in any dimension. In this paper, we prove that a randomized construction of the Delaunay tree (and, thus, of the Delaunay triangulation) can be done in O(n log n) expected time in the plane and in O(n⌈ d 2 ⌉) expected time in d-dimensional space. These results are optimal for fixed d. The algorithm is extremely simple and experimental results are given.

ICRA Conference 1992 Conference Paper

Motion planning for spider robots

• Jean-Daniel Boissonnat
• Olivier Devillers
• LeonBattista Donati
• Franco P. Preparata

The authors consider a simple instance of the problem of planning motions of legged robots. The robot is modeled as a point where all its legs are attached, and the footholds where the robot can securely place its feet consist of a set of points in the plane. Efficient algorithms to compute stable motions in such situations are presented. >

ICRA Conference 1992 Conference Paper

Shortest paths of bounded curvature in the plane

• Jean-Daniel Boissonnat
• André Cérézo
• Juliette Leblond

Given two oriented points in the plane, the authors determine and compute the shortest paths of bounded curvature joining them. This problem has been solved by L. E. Dubins (1957) in the no-cusp case, and by J. A. Reeds and L. A. Shepp (1990) with cusps. A solution based on the minimum principle of Pontryagin is proposed. The approach simplifies the proofs and makes clear the global or local nature of the results. The no-cusp case and the more difficult case with cusps are discussed. >

ICRA Conference 1989 Conference Paper

On the order induced by a set of rays: application to the probing of nonconvex polygons

• Panagiotis Alevizos
• Jean-Daniel Boissonnat
• Mariette Yvinec

The authors present a strategy for discovering the exact shape of a simple (but not necessarily convex) polygon by means of a minimal number of simple probes. When each probe outcome consists of a contact point, a ray measuring that point and the normal to the object at the point, it is shown that 3n-3 probes are necessary and sufficient to discover the exact shape of a polygon with n noncollinear edges. Each probe can be determined in O(log n) time, yielding on O(n log n)-time O(n)-space algorithm. >

ICRA Conference 1988 Conference Paper

A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles

• Francis Avnaim
• Jean-Daniel Boissonnat
• Bernard Faverjon

A general and simple algorithm is presented which computes the set FP of all free configurations for a polygonal object I (with m edges) which is free to translate and/or to rotate but not to intersect another polygonal object E. The worst-case time complexity of the algorithm is O(m/sup 3/n/sup 3/ log mn), which is close to optimal. FP is a three-dimensional curved object which can be used to find free motions within the same time bounds. Two types of motion have been studied in some detail. Motion in contact, where I remains in contact with E, is performed by moving along the faces of the boundary of FP. By partitioning FP into prisms, it is possible to compute motions when I never makes contact with E. In this case, the theoretical complexity does not exceed O(m/sup 6/n/sup 6/ alpha (mn)) but it is expected to be much smaller in practice. In both cases, pseudo-optimal motions can be obtained with a complexity increased by a factor log mn. >

ICRA Conference 1988 Conference Paper

Representing stereo data with the Delaunay triangulation

• Jean-Daniel Boissonnat
• Olivier D. Faugeras
• Elisabeth Le Bras-Mehlman

A coherent way of interpolating 3-D data obtained by stereo, for example, with a simplicial polyhedral surface is discussed. The method is based on constrained Delaunay triangulation; the polyhedral surface is obtained by using a simple visibility property to mark tetrahedra likely to be empty. The method is intrinsically discontinuity-preserving and yields both a surface representation of objects and a volume representation of free space which may be useful in robotics. Algorithms to implement the method are described and their complexity analyzed in the worst case and average case situations where tools of probabilistic geometry are used. >

ICRA Conference 1988 Conference Paper

Scene reconstruction from rays application to stereo data

• Jean-Daniel Boissonnat
• Olivier Monga

The problem of reconstructing shapes of objects from sparse measurements such as points on the boundary of an object is considered. In most situations, the points are the endpoints of a curve or a ray which does not cross the objects. For example, if the sensor is an optical device, the ray is the straight line (the optical ray) joining the camera center to the point. It is shown that the information provided by rays is crucial when determining the shapes of objects, and nonheuristic reconstruction methods in 2-D and 3-D space are described. An efficient method is derived for the reconstruction of surfaces from 3-D segments provided by a stereo vision process. >