Computational Geometry

Items from 1 to 6 out of 6 results

article

Bundling three convex polygons to minimize area or perimeter

Dongwoo Park, Sang Won Bae, Helmut Alt, Hee-Kap Ahn

Computational Geometry > 2016 > 51 > C > 1-14

Given three convex polygons having n vertices in total in the plane, we consider the problem of finding a translation for each polygon such that the translated polygons are pairwise disjoint and the area or the perimeter of their convex hull is minimized. We present the first O(n2)-time algorithm that finds optimal translations of input polygons using O(n2) space for this problem.

article

On the edge crossing properties of Euclidean minimum weight Laman graphs

Sergey Bereg, Seok-Hee Hong, Naoki Katoh, Sheung-Hung Poon, more

Computational Geometry > 2016 > 51 > C > 15-24

This paper is concerned with the crossing number of Euclidean minimum-weight Laman graphs in the plane. We first investigate the relation between the Euclidean minimum-weight Laman graph and proximity graphs, and then we show that the Euclidean minimum-weight Laman graph is quasi-planar and 6-planar. Thus the crossing number of the Euclidean minimum-weight Laman graph is linear in the number of points.

article

Bottleneck partial-matching Voronoi diagrams and applications

Matthias Henze, Rafel Jaume

Computational Geometry > 2016 > 51 > C > 40-54

We study the minimization of the bottleneck distance between a point set B and an equally-sized subset of a point set A under translations. We relate this problem to a Voronoi-type diagram and derive polynomial bounds for its complexity that are optimal in the size of A. We devise efficient algorithms for the construction of such a diagram and its lexicographic variant, which generalize to higher...

article

Convex blocking and partial orders on the plane

José Miguel Díaz-Báñez, Marco A. Heredia, Canek Peláez, J. Antoni Sellarès, more

Computational Geometry > 2016 > 51 > C > 55-66

Let C={c1,…,cn} be a collection of disjoint closed bounded convex sets in the plane. Suppose that one of them, say c1, represents a valuable object we want to uncover, and we are allowed to pick a direction α∈[0,2π) along which we can translate (remove) the elements of C, one at a time, while avoiding collisions. We study the problem of finding a direction α0 such that the number of elements that...

article

Finding largest rectangles in convex polygons

Sergio Cabello, Otfried Cheong, Christian Knauer, Lena Schlipf

Computational Geometry > 2016 > 51 > C > 67-74

We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with n vertices. We give exact algorithms that solve these problems in time O(n3). We also give (1−ε)-approximation algorithms that take time O(ε−1/2log⁡n+ε−3/2).

article

A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares

Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, more

Computational Geometry > 2016 > 51 > C > 25-39

We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen [9] introduced this problem as the geometric version of the unique coverage problem,...

Filter options

Number:
C
Volume:
51
Year:
2016

Publication date

Set your own date range

Keywords

CONVEX POLYGON (2)
(K,L)-SPARSE GRAPHS (1)
ALGORITHMS (1)
APPROXIMATION ALGORITHM (1)
BIPARTITE GRAPH (1)
BOTTLENECK MATCHING (1)
CONVEX BLOCKING (1)
DUAL SPACE (1)
DYNAMIC PROGRAMMING (1)
EXACT ALGORITHM (1)
GEOMETRIC OPTIMIZATION (1)
INSCRIBED RECTANGLE (1)
K-PLANARITY (1)
LAMAN GRAPHS (1)
MULTIGRAPHS (1)
OPTIMIZATION (1)
PACKING PROBLEM (1)
PARTIAL ORDERS (1)
PARTIAL POINT MATCHING UNDER TRANSLATIONS (1)
PLANE GRAPHS (1)
POLYNOMIAL-TIME APPROXIMATION SCHEME (1)
QUASI-PLANARITY (1)
SHIFTING STRATEGY (1)
UNIQUE COVERAGE PROBLEM (1)
VORONOI-TYPE DIAGRAM (1)
more

INFONA - science communication portal

Computational Geometry

Bundling three convex polygons to minimize area or perimeter

On the edge crossing properties of Euclidean minimum weight Laman graphs

Bottleneck partial-matching Voronoi diagrams and applications

Convex blocking and partial orders on the plane

Finding largest rectangles in convex polygons

A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options