Accepted Papers
Download the Booklet of Abstracts.
Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axesaligned line segments
[+]
Abstract:
In this paper we study the mostdemanding predicate for computing
the Euclidean Voronoi diagram of axesaligned line segments, namely
the Incircle predicate.
In particular, we show that the Incircle
predicate can be answered by evaluating the signs of algebraic
expressions of degree at most 6; this is half the algebraic degree
we get when we evaluate the Incircle predicate using the
current stateoftheart approach.
Simplified MedialAxis Approximation with Guarantees
[+]
Abstract:
We present an algorithm that approximates the medial axis of a manifold in R^{3} given by a sufficiently dense point sample. The resulting, nondiscrete approximation converges to the medial axis as the sampling density approaches infinity and we establish a homotopy between the canonical parameterizations of both
structures. While there is no subquadratic upper bound on the output complexity of previous algorithms for nondiscrete medial axis approximation, the output of our algorithm is guaranteed to be of linear size. The algorithm is (arguably) simpler than previous approaches and practically efficient.
The ErdősSós Conjecture for Geometric Graphs
[+]
Abstract:
Let f(n,k) be the minimum number of edges
that must be removed from a complete geometric
graph G on n points, so that there
exists a tree on k vertices that is no
longer a planar subgraph of G.
In this paper we show that
( [1/2] )[(n^{2})/(k−1)]−[n/2] ≤ f(n,k) ≤ 2 [(n(n−2))/(k−2)]−n.
For the case when k=n, we show that
2 ≤ f(n,n) ≤ 3. For the case when
k=n and G is a geometric graph on a set of points
in convex position, we show that at least
three edges must be removed.
Coloring and Guarding Arrangements
[+]
Abstract:
Given an arrangement of lines in the plane, what is the minimum number c of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c, as well as some of its variations. We cast these problems as characterizing the chromatic and the independence numbers of a new family of geometric hypergraphs.
Computer Generation of TriplyCrossing Tile Patterns
[+]
Abstract:
This paper presents an algorithm for generating new tiling patterns in which
three streams of tiles cross without overlap or gaps. For given three tiles,
their copies are placed in three different directions, gradually changing
their shapes so that they cross at the center. The algorithm is based on
periodic tiling of hexagons, morphing between two tiles, and mixing of two
or more curves. The proposed method might give a new direction of extension
of tiling art started by M. C. Escher.
Allmaximum and allminimum problems under some measures
[+]
Abstract:
In this paper we investigate the following type of proximity problems: given a set of n points in the plane P = {p_{1}, p_{2}, p_{3}, . . ., p_{n}}, for each point p_{i} find a pair {p_{j}, p_{k}}, where i ≠ j, k,such that a measure M defined on the triplet of points {p_{i}, p_{j}, p_{k}} is maximized or minimized. The cases where M is the distance from p_{i} to the segment or line defined by {p_{j}, p_{k}} have been extensively studied. We study the cases where M is the sum, product or the difference of the distances from p_{i} to the points p_{j} and p_{k}; the area, perimeter of the triangle defined by p_{i}, p_{j} and p_{k}, as well as the radius of the circumcircle defined by them. We also revisit the problem for the linedistance measure.
MemoryConstrained Algorithms for Simple Polygons
[+]
Abstract:
A constantworkspace algorithm has readonly access to an input array and may use only O(1) additional words of O(logn) bits, where n is the input size.We show how to triangulate a plane straightline graph with n vertices in O(n^{2}) time and constant workspace. We also consider the problem of preprocessing a simplengon P for shortest path queries, where P given by the ordered sequence of its vertices. For this, we relax the space constraint to allow s words of workspace. After quadratic preprocessing, the shortest path between any two points inside P can be found in O(n^{2}/s) time.
What makes a Tree a Straight Skeleton?
[+]
Abstract:
Let G be a cyclefree connected straightline graph with predefined edge lengths and fixed order of incident edges around each vertex. We address the problem of deciding whether there exists a simple polygon P such that G is the straight skeleton of P. We show that for given G such a polygon P might not exist, and if it exists it might not be unique. For small star graphs and caterpillars we give necessary and sufficient conditions for constructing P.
ErdősSzekeres is NPhard in 3 dimensions  and what now?
[+]
Abstract:
The ErdösSzekeres theorem states that, for every k, there is a number n_{k} such that every set of n_{k} points in general position in the plane contains a subset of k points in convex position. If we ask the same question for subsets whose convex hull does not contain any other point from the set, this is not true: as shown by Horton, there are sets of arbitrary size that do not contain an empty 7gon.
These questions have also been studied extensively from a computational point of view, and polynomial time algorithms for finding the largest (empty) convex set have been given for the planar case. In higher dimension, it is not known how to compute such a set efficiently. In this paper, we show that already in 3 dimensions no polynomial time algorithm exists for determining the largest (empty) convex set (unless P=NP), by proving that the corresponding decision problem is NPhard. This answers a question by Dobkin, Edelsbrunner and Overmars from 1990.
As a corollary, we derive a similar result for the closely related problem of testing weak epsnets in R^{3}. Answering a question by Chazelle et al. from 1995, our reduction shows that the problem is coNPhard.
Finally, we make several suggestions for further research on the subject.
Approximating Tverberg Points in Linear Time for Any Fixed Dimension
[+]
Abstract:
Let P be a ddimensional npoint set. A Tverbergpartition of P is a partition of P into r sets P_{1}, ..., P_{r} such that the convex hulls ch(P_{1}), ...,ch(P_{r}) have nonempty intersection. A point in the intersection of the ch(P_{i}) is called a Tverberg point of depth r for P. A classic result by Tverberg implies that there always exists a Tverberg partition of size n/(d+1), but it is not known how to find such a partition in polynomial time. Therefore, approximate solutions are of interest. We describe a deterministic algorithm that finds a Tverberg partition of size n/4(d+1)^{3} in time d^{O(logd)} n. This means that for every fixed dimension we can compute an approximate Tverberg point (and hence also an approximate center point)in linear time. Our algorithm is obtained by combining a novel lifting approach with a recent result by Miller and Sheehy.
Grid Representations and the Chromatic Number
[+]
Abstract:
A grid drawing of a graph maps vertices to grid points
and edges to line segments that avoid such points but
the extremes. First, we determine the maximal number
of grid points that must lie on a line segment of
a grid drawing. This number is closely connected to
the chromatic number. Second, we study how many
columns we need to draw a graph in the grid, introducing
some new NPcomplete problems. Finally, we
show that any planar graph has a planar grid drawing
where every line segment contains exactly two grid
points. This result proves conjectures asked by David
FloresPenaloza and Francisco Javier Zaragoza Martinez.
EnergyAware Art Gallery Illumination
[+]
Abstract:
We consider a variant of the Art Gallery Problem, where a polygonal
region is to be covered with light sources that emit light fading with
distance. We describe a practical approximation algorithm based on the simplex
method and primaldual LP separation. For the case where the light
positions are given, we describe a fully polynomialtime approximation scheme.
Noncrossing Connectors in the Plane
[+]
Abstract:
We consider the noncrossing connectors problem, which is stated as follows: Given n simply connected regions R_{1},...,R_{n} in the plane and finite point sets P_{i} subset of R_{i} for i=1,...,n, are there noncrossing connectors y_{i} for (R_{i},P_{i}), i.e., arcconnected sets y_{i} with P_{i} subset of y_{i} subset of R_{i} for every i=1,...,n such that y_{i} and y_{j} are disjoint for all i different from j?
We prove that noncrossing connectors do always exist if the regions form a collection of pseudodisks, i.e., the boundaries of every pair of regions intersect at most twice. We provide a simple polynomialtime algorithm if the regions are axisaligned rectangles. Finally we prove that the general problem is NPcomplete, even if the regions are convex, the boundaries of every pair of regions intersect at most four times and P_{i} consists of only two points on the boundary of R_{i} for i=1,...,n.
Augmentability to Cubic Graphs
[+]
Abstract:
We consider the problem of adding edges to a given graph in order to make it cubic (i.e., all vertices have degree 3). As a first result, we show that the problem is NPcomplete if the resulting graph is required to be simple and planar. In the reduction, we rely on edges whose combinatorial embedding is not determined by the graph. Further, we show that the problem of deciding whether additional edges can be drawn on a given (embedded) plane geometric graph, in a way that the resulting plane geometric graph is cubic, is NPcomplete. The problem remains NPcomplete even if the initial graph is connected.
Proximity graphs: E, δ, Δ, χ and ω
[+]
Abstract:
Graphtheoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. Then we focus on the higher order versions of some of these graphs and give bounds on the same properties.
Coloring Dynamic Point Sets on a Line
[+]
Abstract:
We consider a coloring problem on dynamic, onedimensional point sets: points appearing and disappearing on a line at given times. We wish to color them with k colors so that at any time, any sequence of p(k) consecutive points, for some function p, contains at least one point of each color.
We prove that no such function p(k) exists in general. However, in the restricted case in which points appear gradually, but never disappear, we give a coloring algorithm guaranteeing the property at any time with p(k)=8k−5.
This can be interpreted as coloring point sets in R^{2} with k colors such that any bottomless rectangle containing at least 8k−5 points contains at least one point of each color. Chen et al. (2009) proved that such colorings do not always exist in the case of general axisaligned rectangles. Our result also complements recent contributions from Keszegh and Pálvölgyi (2011).
Maxmin Length Triangulation in Polygons
[+]
Abstract:
We consider the maxmin length triangulation problem in polygons. We give an NPhardness proof for the case of polygons with holes and interior points. For simple polygons we present an optimal algorithm using dynamic programming.
Homotopic Coriented Routing
[+]
Abstract:
We study the problem of finding noncrossing Coriented paths that use as few links as possible and are homotopic to a set of input paths in an environment with Coriented obstacles. We introduce a special type of Coriented pathssmooth pathsand present a 2approximation algorithm that runs in O(n^{2} (n + logκ) + k_{in} logn) time, where n is the total number of paths and obstacle vertices, k_{in} is the total number of links in the input, and κ = C. The algorithm also computes an O(κ)approximation for general Coriented paths. As a related result we show that, given a set of (possibly crossing) Coriented paths with a total of L links, noncrossing Coriented paths homotopic to the input paths can require a total of Ω(L logκ) links.
A Lower Bound for Shallow Partitions
[+]
Abstract:
We give a lower bound of Ω(log(n/k)/loglog(n/k)) for the crossing number of shallow partitions in the plane
Colored Quadrangulations with Steiner Points
[+]
Abstract:
Let P be a kcolored set of n points in general position on the plane, where k ≥ 2. A kcolored quadrangulation of P is a maximal straightedge plane graph with vertex set P satisfying the property that every interior face is a properly colored quadrilateral, i.e., no edge connects vertices of the same color. It is easy to check that in general not every set of points admits a kcolored quadrangulation, and hence the use of extra points, known in the literature as Steiner points, is required in order to obtain one. In this paper, we show that if P satisfies some condition for the colors of the points in Conv(P), then a kcolored quadrangulation of P can always be constructed using less than [((16 k−2) n+7 k−2)/(39 k−6)] Steiner points. Our upper bound improves the previously known upper bound for k=3, and represents the first bounds for k ≥ 4.
Upward planar embedding of a nvertex oriented path into O(n^{2}) points
[+]
Abstract:
We prove that every oriented path with n vertices admits an upward
planar embedding into every set of n^{2}−n points in general
position.
On Ellipsoidal Approximations of Zonotopes
[+]
Abstract:
We adapt the Goffin's Algorithm for construction of
the LöwnerJohn ellipsoid for a fulldimensional zonotope
given by the generator description.
Unsolvability of the Weighted Region Shortest Path Problem
[+]
Abstract:
Let S be a subdivision of the plane into polygonal regions, where each region has an associated positive weight. The weighted region shortest path problem is to determine a shortest path in S between two points s,t ∈ S, where the distances are measured according to the weighted Euclidean metric  the length of a path is defined to be the weighted sum of (Euclidean) lengths of the subpaths within each region. We show that this problem cannot be solved in the Algebraic Computation Model over the Rational Numbers (ACMQ). The ACMQ can compute exactly any number that can be obtained from the rationals Q by applying a finite number of operations from +, −, ×, ÷, ^{k}√, for any integer k ≥ 2. Our proof uses Gröbner bases and Galois theory, and is based on Bajaj's technique.
An extension of a Theorem of Yao & Yao
[+]
Abstract:
Let μ be a nice measure in R^{d}. A theorem of Yao and Yao states that R^{d} can be partitioned into 2^{d} parts of equal μmeasure such that every hyperplane avoids at least one element of the partition. We extend this result to the case when every hyperplane is required to avoid two elements of the partition, this can be done by partitioning R^{d} into 3 ·2^{d−1} parts of equal μmeasure. Then we use this to obtain a result on a problem about the separation of points and hyperplanes.
TriangleTriangle Tolerance Tests
[+]
Abstract:
The motivation for this work comes from the digital mockup process in car industry where constructions and motions in the design of a car are evaluated. One important task is to verify that moving components keep a given distance to other (stationary) components in their environment. The geometry of a component is described by a high quality triangle mesh and its trajectory is specified by a discrete sequence of positions and orientations. Solving this task, the basic operation is a triangletriangle tolerance test:Given two triangles, determine whether their shortest distance is greater than a given tolerance value ε. A special case is the triangletriangle intersection test choosing ε = 0. For the latter a lot of work has been done to solve it efficiently [2, 3, 4, 5]. We present efficient solutions for the generalized question. Our solutions are optimized for the treatment of millions of triangletriangle tolerance tests in parallel on multicore CPU and on the GPU.
Optimizing the computation of sequences of determinantal predicates
[+]
Abstract:
The orientation predicate is the core procedure in many important geometric algorithms, such as convex hull and triangulation computations. As the dimension of the computation space grows, a higher percentage of the computation time is consumed by these predicates. In this paper we study the computation of sequences of determinantal predicates in a signle or a sequence of convex hull computations.
We propose a method that improves the amortized complexity of the determinants involved in a convex hull computation. Moreover, we study how can we use the computation done in a convex hull construction to improve the construction of subsequent convex hulls. Our two main tools are the dynamic determinant computation and the reusage of determinantal minors. Finally, we implement a simple method that optimizes the computation of subsequent determinantal predicates in both single and sequence of convex hull computations. The experiments show in the single convex hull scenario a speedup up to dimension 5 and in sequences of convex hulls a speedup of 100 times when the dimension is 6.
Exact and approximate algorithms for resultant polytopes
[+]
Abstract:
We develop an incremental algorithm to compute the Newton polytope of the resultant, aka resultant polytope, or its projection along a given direction. Our algorithm exactly computes vertex and halfspacerepresentations of the resultant polytope using an oracle producing resultant vertices in a given direction. It is outputsensitive as it uses one oracle call per vertex. We implement our algorithm using the experimental CGAL package triangulation. A variant of the algorithm computes successively tighter inner and outer approximations: when these polytopes have, respectively, 90% and 105% of the true volume, runtime is reduced up to 25 times. Compared to tropical geometry software, ours is faster up to dimensions 5 or 6, and competitive in higher dimensions. Compared to lrs, cdd, and polymake, the computation of convex hull is fastest along with polymake. The resultant is fundamental in algebraic elimination and in implicitizing parametric hypersurfaces: we compute the Newton polytope of surface equations in < 1sec, when there are < 100 terms in the parametric polynomials, which includes all common instances in geometric modeling. Our method computes instances of 5, 6 or 7dimensional polytopes with 35K, 23K or 500 vertices, respectively, in < 2hr.
Domain Mapping using Harmonic Functions in nonconvex domains of genus nonzero
[+]
Abstract:
Many geometric processing tasks can be performed efficiently on regular domains. As complex, nonconvex, realworld geometries come into play, however, this efficiency is often lost and sometimes there may be no method to find a solution. Domain Mapping aims to construct some map from a geometrically complicated space to a simple, usually convex, space. Once this map is constructed, solutions can be found in the
new target domain and transferred back to the original domain. Some problems that benefit from domain mapping include mesh construction, robot path planning and computer animation. This paper outlines a method to perform domain mapping using harmonic functions, following which an extension is presented that allows it to handle 2D domains containing voids.
Properties and Algorithms for Line Location with Extensions
[+]
Abstract:
In this work we extend some wellknown properties
for simple line location  namely an incidence and a
halving property  to a more general setting and use
them to develop algorithms in order to approximate a
set of n given points by one or more lines. This yields
an O(n^{4/3} logn) (O(n^{2})) algorithm for locating a single
line minimizing the sum of (weighted) distances
to the n points for pointline distances induced by
a norm. A trimmed line which minimizes the sum
of (weighted) distances to the m ≤ n closest of the
n points can be found in O(n^{2} logn) (O(n^{3})) time.
Finally, K lines minimizing the sum of distances of
each of the n points to the closest line is computed
in O(n^{2K+1} (K + logn)) time, where the logn factor
only applies to the trimming case.
On the orderk Voronoi diagram of line segments
[+]
Abstract:
We analyze the structural properties of the orderk Voronoi diagram of n linesegments. We show that orderk Voronoi regions may disconnect to Ω(n) faces. Nevertheless, the overall structural complexity of the orderk linesegment Voronoi diagram remains O(k(n−k)), similarly to its counterpart for points.
The expected number of points in circles
[+]
Abstract:
Let S be a plane point set of n points with no three of them collinear and no four cocircular.
Consider the circle passing through three points of S chosen uniformly at random and let X be the random variable that counts the number of points of S inside this circle. We show that expectation E_{S}(X) and variance V_{S}(X) of X only depend on the rectilinear crossing number cr(S) of S. More precisely, E_{S}(X) = [cr(S)/(n  3)] + [(n−3)/4] and
Then, consider the smallest circle containing two points of S chosen uniformly at random, and let Y be the random variable that counts the number of points of S inside this circle. We show an upper bound on the expectation E_{S}(Y) ≤ [(n−2)/3], and there are point sets S attaining this bound.

Many collinear ktuples with no k+1 collinear points
[+]
Abstract:
For every k > 3, we give a construction of planar point sets with many collinear ktuples and no collinear (k+1)tuples.
Selection of Extreme Points and Halving Edges of a Set by its Chirotope
[+]
Abstract:
Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the set's chirotope, as source of information. We answer this question in the affirmative for sets realizable in the Euclidean plane. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time.
A Fixed Parameter Algorithm for Guarding 1.5D Terrains
[+]
Abstract:
In the 1.5D terrain guarding problem we are given a polygonal region in the plane determined by an xmonotone polygonal chain, and the objective is to find the minimum number of guards for the given input terrain.The only previous theoretical results about this problem are about approximation. We turn to fixedparameter tractability.
We study "depth of terrain onion peeling" as parameter and show that 1.5D terrain guarding problem is fixedparameter tractable with respect to this parameter
Some Sparse Yao Graphs are Spanners
[+]
Abstract:
We show that, for any integer k > 2, the SparseYao graph (also known as YaoYao graph) YY_{4k} constructed under the L_{∞} norm, is a spanner.
TopologyPreserving Watermarking of Vector Data
[+]
Abstract:
The embedding of a digital watermark in vector data results in a perturbation of the vertices which needs to be constrained in order to maintain geometric properties of the data. In this paper we investigate the problem of computing socalled perturbation regions in which the vertices of a planar straightline graph may be dislocated while still preserving the topology of the input. We propose two different algorithms to solve this problem and discuss how they can form the geometric part of a watermarking framework.
Aligned Matched Drawability of Some Graph Triples
[+]
Abstract:
In this paper we extend the concept of matched drawability to aligned matched drawability of triple and quadruples of graphs and develop algorithms for constructing such drawings for quadruples and triples of wheels. We also introduce a new class of graphs called doublerim wheel and develop algorithms for constructing aligned matched drawing for triples consisting of two wheels and a tree or a doublerim wheel.
The graphs that can be drawn with one bend per edge
[+]
Abstract:
We provide a precise description of the class of graphs that admit an
onebend drawing, i.e., an orthogonal drawing with at most one bend
per edge. The main tools for the proof are Eulerian orientations and
discrete harmonic functions.
Covering spaces and Delaunay triangulations of the 2D flat torus
[+]
Abstract:
A previous algorithm was computing the Delaunay triangulation of the flat torus, by using a 9sheeted covering space. We propose a modification of the algorithm using only a 8sheeted covering space, which allows to work with 8 periodic copies of the input points instead of 9. The main interest of our contribution is not only this result, but most of all the method itself: this new construction of covering spaces generalizes to Delaunay triangulations of surfaces of higher genus.
A Linear Time Algorithm for the QueueNumbers of Maximal Outerplanar Graphs
[+]
Abstract:
We present a linear time algorithm for computing the queuenumbers of maximal outerplanar graphs.
On the reconstruction of convex sets from random normals measurements
[+]
Abstract:
We study the problem of reconstructing convex sets using only a finite number of measurements of normal vectors. More precisely, we suppose that the normal vectors we are measuring come from independent random points uniformly distributed along the boundary of our convex sets. Given a target Hausdorff error epsilon, we are interested in upper bounding on the number of probes that one has to perform in order to obtain an epsilonapproximation of this convex with high probability. Our results makes use of the stability theory related to Minkowski's theorem.
Delaunay triangulations on the word RAM: Towards a practical worstcase optimal algorithm
[+]
Abstract:
The Delaunay triangulation of n points in the plane can be constructed in o(n logn) time when the coordinates of the points are integers from a restricted range. However, algorithms that are known to achieve such running times had not been implemented so far. We explore ways to obtain a practical algorithm for Delaunay triangulations in the plane that runs in linear time for small integers. For this, we first implement and evaluate variants of an algorithm, BrioDC, that is known to achieve this bound. We find that our implementations of these algorithms are by a reasonable constant factor slower than the fastest known algorithms. Secondly, we implement and evaluate variants of an algorithm, BRIO, that runs fast in experiments. Our variants aim to avoid bad worstcase behavior, but contrary to our expectation, they do not improve the running time.
Lines Through Segments in Three Dimensional Space
[+]
Abstract:
We present an efficient outputsensitive algorithm and its exact
implementation to solve the following problem: Given a set S of
n line segments in threedimensional space, find all the lines that
simultaneously intersect quadruples of line segments in S. We
refer to this problem as `the linesthroughsegments problem', or
LTS for short. The algorithm properly handles all degenerate
cases. Since we do not assume general position, we compute all lines
that intersect at least four segments in S. The algorithm
runs in O((n^{3} + I)logn) time, and requires O(n + I) working
space, where I is the output size; I is bounded by O(n^{4}). We use
CGAL arrangements and in particular its support for twodimensional
arrangements in the plane and on the sphere to efficiently compute the
intersecting lines in an exact manner.
We also report on the performance of our algorithm and its
implementation compare it to others.
The source code of the LTS program as well as the input
examples for the experiments can be obtained from
http://acg.cs.tau.ac.il/projects/lts.
Locally Correct Fréchet Matchings
[+]
Abstract:
The Fréchet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to "natural" matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such a matching exists for two polygonal curves and give an algorithm to compute it.
On the Farthest LineSegment Voronoi Diagram
[+]
Abstract:
The farthest linesegment Voronoi diagram shows properties surprisingly different than the farthest point Voronoi diagram: Voronoi regions may be disconnected and they are not characterized by convexhull properties. In this paper we introduce the farthest linesegment hull, a cyclic structure that relates to the farthest linesegment Voronoi diagram similarly to the way an ordinary convex hull relates to the farthestpoint Voronoi diagram and provide O(n log n)time algorithms for its construction. Using the farthest linesegment hull, we derive a tighter bound on the (linear) size of the farthest linesegment Voronoi diagram. We also illustrate properties of the L_{∞} farthest linesegment Voronoi diagram, which finds applications in VLSI Design Automation.
Kinetic Collision Detection for LowDensity Scenes in the BlackBox Model
[+]
Abstract:
We present an efficient method for collision detection
in the blackbox KDS model for a set S of n objects in
the plane. In this model we receive the object locations at regular time steps and we know a bound d_{max}
on the maximum displacement of any object within
one time step. Our method maintains, in O((λ+ k)n)
time per time step, a compressed quadtree on the
boundingbox vertices of the objects; here λ denotes
the density of S and k denotes the maximum number
of objects that can intersect any disk of radius d_{max} .
Collisions can then be detected by testing O((λ+k)^{2} n)
pairs of objects for intersection.
On the Exploration Problem for Polygons with One Hole
[+]
Abstract:
We study online strategies for autonomous mobile
robots with vision to explore unknown polygons with
at most one hole. We prove lower bounds on the competitive ratio of such strategies both for the orthogonal and the general case. Furthermore we describe a
competitive strategy for the case that the robot can
distinguish between the edges of the outer boundary
and the hole.
Revisiting the Construction of SSPDs in the Presence of Memory Hierarchies
[+]
Abstract:
We revisit the randomized internalmemory algorithm of Abam and HarPeled for constructing a semiseparated pair decomposition (SSPD) of N points in R^{d} in the context of the cacheoblivious model of computation.
Their algorithm spends O(N ϵ^{−d} log_{2}N) time (assuming that the floor function can be evaluated in constant time, O(N ϵ^{−d} log^{2}_{2} N) time otherwise) in expectation and produces a linearsized SSPD in which each point participates in only a logarithmic number of pairs with high probability.
Using a modified analysis of their algorithm and several cacheoblivious techniques for tree construction, labeling, and traversal, we obtain a cacheoblivious algorithm that spends an expected number of O(sort(Nϵ^{−d}) log_{2} N) memory transfers.
On Triangulation Axes of Polygons
[+]
Abstract:
We define the triangulation axis of a simple polygon P as an anisotropic medial axis of P whose 'unit disks' are line segments or triangles. The underlying triangulation that specifies the anisotropy can be varied, to adapt the axis so as to reflect predominant geometrical and topological features of P. Triangulation axes are piecewise linear skeletons, and typically have much fewer edges and branchings than the Euclidean medial axis or the straight skeleton of P (between n−2 and 2n−6 edges, compared to 2n−3). Still, they retain important properties, as for example the reconstructability of P from its skeleton. Triangulation axes can be easily computed from their defining triangulations in O(n) time. We investigate the effect of using several optimal triangulations for P. In particular, careful edge flipping in the constrained Delaunay triangulation leads, in O(n logn) overall time, to an axis competitive to high quality axes requiring O(n^{3}) time for optimization via dynamic programming.
Maximizing kinfluence regions
[+]
Abstract:
Let S be a finite set of points included in a bounded polygonal domain D
of the plane. The orderk nearest influence region of a point in S is the
set
of points of D having the given point between their knearest neighbors in
S.
Let P be a weighted partition of the domain D into
polygonal regions, each region with an associated nonnegative weight.
We want to solve the problem of finding a new point s of D such that
maximizes the weighted area of its
orderk nearest influence region with respect to S ∪{s}, that is
the sum of the weighted areas of the regions obtained intersecting the
orderk nearest influence region with the regions of P.
We present a GPU parallel approach, designed under CUDA architecture,
for approximately solving the problem and also provide experimental results
obtained with its implementation that show the efficiency and
scalability of the approach.
Onetoone Point Set Matchings for Grid Map Layout
[+]
Abstract:
We study several onetoone point set matching problems which are motivated
by layout problems for grid maps. We are given two sets A and B of n
points in the plane, and we wish to compute an optimal onetoone matching
between A and B. We consider two optimisation criteria: minimising the
sum of the L_{1}distances between matched points, and maximising the number
of pairs of points in A for which the matching preserves the directional
relation. We show how to minimise the total L_{1}distance under translation
or scaling in O(n^{6} log^{3} n) time, and under both translation and scaling in
O(n^{10} log^{3} n) time. We further give a 4approximation for preserving
directional relations by computing a minimum L_{1}distance matching in
O(n^{2} log^{3} n) time.
Optimally solving a general transportation problem using Voronoi diagrams
[+]
Abstract:
Let S be a set of n point sites in R^{d}. A bounded set C ⊂ R^{d} is to be distributed among the sites p ∈ S such that (i), each p receives a subset C_{p} of prescribed volume and (ii), the average distance of all points z of C from their respective sites p is minimized.
In our model, volume is quantified by a measure μ, and the distance between a site p and a
point z is given by a function d_{p}(z).
Under quite liberal technical assumptions on C and on the functions d_{p}(·) we show that a solution
of minimum total cost can be obtained by intersecting with C the Voronoi diagram of the sites in S,
based on the functions d_{p}(·) equipped with suitable additive weights.
Moreover, this optimum partition is unique, up to subsets of C of measure zero.
Unlike the the deep analytic methods of classical transportation theory, our proof is based on
direct geometric arguments.
How Many Potatoes are in a Mesh?
[+]
Abstract:
We consider the combinatorial question of how many convex polygons
can be made by unions of triangles taken from a fixed triangulation.
For general triangulations there can be exponentially many, but if
the triangulation is fat (every triangle has its angles lower
bounded by a fixed constant δ > 0), then there can only be
polynomially many.
We provide both lower and upper bounds in both settings.
Higher Order City Voronoi Diagrams
[+]
Abstract:
We investigate the higherorder Voronoi diagrams in the L_{1} metric in the presence of a transportation network, which is commonly referred to as city metric.
For the structural complexity of kthorder city Voronoi diagrams we show a lower bound of Ω(n+kc) and an upper bound of O(k(n−k)+kc), where c is the complexity of the transportation network. This is quite different from the bound O(k(n−k)) in the Euclidean metric, especially for the case when k=n−1. Furthermore, we develop an O(k^{2}(n+c) logn)time algorithm for the kthorder city Voronoi diagram and an O(nc log^{2}(n+c) logn)time algorithm for the farthestsite city Voronoi diagram.
Equating the witness and restricted Delaunay complexes
[+]
Abstract:
It is a wellknown fact that the restricted Delaunay and witness
complexes may differ when the landmark and witness sets are located
on submanifolds of R^{d} of dimension 3 or more. Currently, the
only known way of overcoming this issue consists of building some
crude superset of the witness complex, and applying a greedy sliver
exudation technique on this superset. Unfortunately, the
construction time of the superset depends exponentially on the
ambient dimension, which makes the witness complex based approach to
manifold reconstruction impractical. This work provides an analysis
of the reasons why the restricted Delaunay and witness complexes
fail to include each other. From this a new set of conditions
naturally arises under which the two complexes are equal.
Compatible Matchings for Bichromatic Plane Straightline Graphs
[+]
Abstract:
Two plane graphs with the same vertex set are compatible if their union
is again a plane graph. We consider bichromatic plane straightline graphs with
vertex set S consisting of the same number of red and blue points,
and (perfect) matchings which are compatible to them.
For several different classes C of graphs,
we present lower and upper bounds
such that any given graph G(S) ∈ C
admits a compatible (perfect) matching with this many disjoint edges.
Canonical ordering for triangulations on the cylinder, with applications to periodic straightline drawings
[+]
Abstract:
We extend the notion of canonical orderings (and underlying Schnyder woods) to cylindric triangulations. This allows us to extend the incremental straightline drawing algorithm of de Fraysseix et al. to this setting. Our algorithm yields in linear time a crossingfree straightline drawing of a cylindric triangulation T with n vertices on a regular grid Z/w Z ×[0,h], with w ≤ 2n and h ≤ n(n−3)/2.
As a byproduct, we can also obtain in linear time a crossingfree straightline drawing of a toroidal triangulation with n vertices on a periodic regular grid
Z/w Z ×Z/h Z, with w ≤ 2n and h ≤ n(n+3)/2.
Planar βskeletons via point location in monotone subdivisions of subset of lunes
[+]
Abstract:
We present a new algorithm for lunebased βskeletons for sets of n points in the plane, for β ∈ (2,∞], the only case when optimal algorithms are not known. The running time of the algorithm is O(n^{3/2} log^{1/2} n), which is the best known and is an improvement of Rao and Mukhopadhyay result. The method is based on point location in monotonic subdivisions of arrangements of curve segments.
Probabilistic Lower Bounds on the Length of a Longest Edge in Delaunay Graphs of Random Points in a dBall
[+]
Abstract:
In this paper, we complete the study of the length of a longest Delaunay edge for points randomly distributed in multidimensional Euclidean spaces carried out in [1]. The Delaunay graph is defined over a set of n points distributed uniformly at random in a ddimensional body of unit volume, assuming that the probability that those points are not in general position is negligible. The motivation to study this problem comes from its application in energyefficient geometric routing and flooding in wireless sensor networks. Given that the length of the longest Delaunay edge is strongly influenced by the boundary of the enclosing region, in [1] we study the problem for the surface of a dsphere and the volume of a dball. The results presented in that work include upper and lower bounds for ddimensional bodies with and without boundaries, that hold for a parametric error probability. Lower bounds for a dball were proved only for d ≤ 3 leaving open the question for higher dimensions. We answer this question in the present work presenting a lower bound that holds in general for any d > 1, and we also compute the particular cases d=2 and d=3 to obtain the precise bound on the euclidean distance. These lower bounds are proved showing that a configuration that yields a Delaunay edge of a certain length occurs with probability at least a parameter epsilon. These lower bounds are computed up to constants and are asymptotically tight for e^{−cn} ≤ ϵ ≤ n^{−c}, for any constant c > 0, and constant d. To the best of our knowledge, the present work and [1] are the first comprehensive study of this problem.
[1] E. Arkin, A. Fernandez Anta, J.S.B. Mitchell, and M.A. Mosteiro. Probabilistic Bounds on the Length of a Longest Edge in Delaunay Graphs of Random Points in dDimensions. CCCG 2011.
Refold Rigidity of Convex Polyhedra
[+]
Abstract:
We show that every convex polyhedron may be unfolded to one planarpiece, and then refolded to a different convex polyhedron.If the unfolding is restricted to cut only edges of the polyhedron,then the dodecahedron is ëdgeunfold rigid" in the sense that allof its 43,380 edge unfoldings may only fold back to the dodecahedron.We begin the exploration of which polyhedra are edgeunfold rigid,identifying one infinite rigid class, perturbed dodecahedra,and one infinite nonrigid class: tetrahedra.A 9page version of this paper, with more figures and all proofsincluded, is available at http://cs.smith.edu/~orourke/Unf/RefoldRigidEuroCGFull.pdf.
On balanced 4holes in bichromatic point sets
[+]
Abstract:
Let S=R∪B be a set of n points in general position in the plane.
The elements of R and B will be called, respectively, the red and blue elements
of S. A khole of S is a simple polygon with k vertices, all in S, and
containing no element of S in its interior.
A 4hole of S is balanced is if it has two blue and two red vertices.
In this paper, we characterize the set of bicolored
points S=R ∪B that have balanced convex
4holes. We also show that if the 4holes of S are
allowed to be nonconvex, then if S=R ∪B, and
R=B, then S always has a quadratic number of
balanced 4holes.
Order type invariant labeling and comparison of point sets
[+]
Abstract:
We consider the problem of computing an order type invariant labeling for a given set of n points.
In 2D, such a labeling can be constructed in O(hn^{2}) time, where h is the size of the smallest convex layer.
In 3D the time complexity is O(n^{3} logn) if the point set is in general position. This is useful to test if two point sets have the same order type within the same time bounds. It can also be used as preprocessing for any order type invariant algorithm, such as triangulation/tetrahedralization, or polygonization.
Book Embedding of Nfree posets
[+]
Abstract:
In this paper we deal with the page number problem for partially ordered sets (posets)
restricted to the family of Nfree posets. We calculate this number exactly for treestructured
Nfree posets and for treestructured Nfree planar posets. Some other results are also mentioned.
On the Rectilinear Convex Layers of a Planar Set
[+]
Abstract:
Let S=p_{1},...,p_{n} be a set of n points in the plane in general position. A quadrant Q of the plane is the intersection of two closed halfplanes whose supporting lines are parallel to the x and yaxes. We say that a quadrant is Sfree if it does not contain any point of S in int(Q), where int(Q) denotes the interior of Q. The rectilinear convex hull RH(S) of S is defined as the plane minus the union of Sfree quadrants.
The rectilinear convex layers of S are defined as follows:
 The first rectilinear convex layer of S, denoted L_{1}, is RH(S). Let S_{1} denote the set of elements of S that belong to RH(S).
 The ith rectilinear convex layer L_{i} of S is the rectilinear convex hull RH(S_{i}), where S_{i} = S \{S_{1} ∪... ∪S_{i1} }, where S_{j} is the set of elements of S in L_{j} . We stop when S \{S_{1} ∪... ∪S_{i} } is empty; the first i for which S \{S_{1} ∪... ∪S_{i} } is empty is the number of rectilinear convex layers of S.
Partial Searchlight Scheduling is Strongly PSPACEcomplete
[+]
Abstract:
The problem of searching a polygonal region for an unpredictably moving intruder by a set of stationary guards, each carrying an orientable laser, is known as the Searchlight Scheduling Problem. Determining the complexity of deciding if the entire area can be searched is a longstanding open problem. Recently, the author introduced the Partial Searchlight Scheduling Problem, in which only a given subregion of the environment has to be searched, and proved that its 3dimensional decisional version is PSPACEhard, even when restricted to orthogonal polyhedra.
Here we extend and refine this result, by proving that 2dimensional Partial Searchlight Scheduling is strongly PSPACEcomplete, both in general and restricted to orthogonal polygons in which the region to be searched is a rectangle.
New separation theorems and subexponential time algorithms for packing and piercing of fat objects
[+]
Abstract:
Let C be a set of n fat objects of arbitrary sizes in R^{d} whose
packing and piercing numbers are denoted by Pack(C),
and Pierce(C), respectively.
We derive the first subexponential time algorithms for computing
the exact value of Pack(C)
and Pierce(C), respectively, in
n^{O( Pack(C)[(d−1)/d])}
and n^{O( Pierce(C)[(d−1)/d])}
time and O(nlogn) storage.
Our methods build upon the separation theorems derived by Chan, and Smith and
Wormald. Specifically, we also derive a 1/3−2/3 measure separation theorem
with relatively small constants
for fat objects, as our mail tool, that is interesting in its own way.
The results readily give rise to polynomial time approximation schemes (PTAS)
that run in n^{O([1/(ϵ)]d−1)} time and O(nlogn) storage
Extremal problems in colored point sets in the plane
[+]
Abstract:
The goal of this paper is to give an overview of the results and open questions in the area of long alternating paths and separated matchings. We also include a new proof of the construction class of Hajnal and Mészáros showing there are at most [4/3]n+O(√n) points in any noncrossing alternating path on a specific convex 2nelement equally twocolored planar point set. This is currently the best upper bound and it is conjectured to be asymptotically tight. The survey is written based on my Ph.D. thesis.
Tighter Bounds on the Size of Optimal Meshes
[+]
Abstract:
The theory of optimal size meshes gives a method for analyzing the output size of a Delaunay refinement mesh in terms of the integral of a sizing function over the space. The input points define a maximal such sizing function called the feature size. Integrating the feature size function over input domain is not easy, and historically, was not deemed necessary. Matching upper and lower bounds in terms of this integral seemed sufficient. However, a new analysis of the feature size integral led to linearsize Delaunay meshes, the Scaffold Theorem relating surface and volume meshes, and a timeoptimal output sensitive point meshing algorithm. The key idea is to consider the pacing of an ordered point set, a measure of the rate of change in the feature size as points are added one at a time. In previous work, Miller et al. showed that if an ordered point set has pacing φ, then the number of vertices in an optimal mesh will be O(φd n), where d is the input dimension. We give a new analysis of this integral showing that the output size is only O(n logφ). The new analysis tightens all of the previous results mentioned above and provides matching lower bounds.
Outerplanar graph drawings with few slopes
[+]
Abstract:
We prove that every outerplanar graph with maximum degree ∆ ≥ 4 has a straightline outerplanar drawing with
at most ∆−1 distinct edge slopes. This bound is tight: for every ∆ ≥ 4 there is an outerplanar graph
of maximum degree ∆ which requires at least ∆−1 distinct edge slopes for its outerplanar straightline drawing.
On the homotopy test on surfaces with boundaries
[+]
Abstract:
Let G be a graph cellularly embedded in a surface S
orientable or not, and with at least a boundary. Given
two closed walks c and d in G, we describe linear time
algorithms to decide if c and d are homotopic in S,
either freely or with fixed basepoint. After O(G) time
preprocessing independent of c and d, our algorithms
answer the homotopy test in O(c + d) time, where
G, c and d are the respective numbers of edges of
G, c and d.
A Uniform Approach to Enumeration of Facets, Enumeration of Vertices and Computation of Volume of a Zonotope
[+]
Abstract:
A uniform approach is proposed to solving three fundamental problems related to zonotopes given by generator description  the facet enumeration, the vertex enumeration and the volume computation. The common algorithmic frame is designed, which allows to solve all the three problems simultaneously. The proposed algorithm is compact for the facet enumeration and volume computation.
On Counting Empty PseudoTriangles in a Point Set
[+]
Abstract:
We address the problem of counting empty pseudotriangles defined by a set of points in the plane. First, we assume that the three convex vertices are fixed, and provide algorithms, which solve the respective problem in O(n^{2}) time using O(n) space, for the cases when the pseudotriangles can be arbitrary or must be starshaped. The relaxation of our assumption increases the time complexity by factor n^{3} in either case.