Maximizing the overlap of two planar convex sets under rigid motions

Hee Kap Ahn; Otfried Cheong; Chong Dae Park; Chan Su Shin; Antoine Vigneron

doi:10.1145/1064092.1064146

Maximizing the overlap of two planar convex sets under rigid motions

Hee Kap Ahn^*, Otfried Cheong, Chong Dae Park, Chan Su Shin, Antoine Vigneron

^*Corresponding author for this work

Computer, Electrical and Mathematical Sciences and Engineering

Research output: Contribution to conference › Paper › peer-review

4 Scopus citations

Abstract

Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any ε > 0, we compute a rigid motion such that the area of overlap is at least 1 -ε times the maximum possible overlap. Our algorithm uses O(l/ε) extreme point and line intersection queries on P and Q, plus O((1/ε²)log(1/ε)) running time. If only translations are allowed, the extra running time reduces to O((1/ε) log(1/ε)). If P and Q are convex polygons with n vertices in total, the total running time is O((1/ε) logn+(1/ε²) log(1/ε)) for rigid motions and O((1/ε) log n + (1/ε) log(1/ε)) for translations.

Original language	English (US)
Pages	356-363
Number of pages	8
DOIs	https://doi.org/10.1145/1064092.1064146
State	Published - 2005
Event	21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italy Duration: Jun 6 2005 → Jun 8 2005

Other

Other	21st Annual Symposium on Computational Geometry, SCG'05
Country/Territory	Italy
City	Pisa
Period	06/6/05 → 06/8/05

Keywords

Approximation algorithm
Convex shape
Pattern matching
Sublinear algorithm

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/1064092.1064146

Cite this

@conference{14cbbfdb38d24424b852a13ee9295eaf,

title = "Maximizing the overlap of two planar convex sets under rigid motions",

abstract = "Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any ε > 0, we compute a rigid motion such that the area of overlap is at least 1 -ε times the maximum possible overlap. Our algorithm uses O(l/ε) extreme point and line intersection queries on P and Q, plus O((1/ε2)log(1/ε)) running time. If only translations are allowed, the extra running time reduces to O((1/ε) log(1/ε)). If P and Q are convex polygons with n vertices in total, the total running time is O((1/ε) logn+(1/ε2) log(1/ε)) for rigid motions and O((1/ε) log n + (1/ε) log(1/ε)) for translations.",

keywords = "Approximation algorithm, Convex shape, Pattern matching, Sublinear algorithm",

author = "Ahn, {Hee Kap} and Otfried Cheong and Park, {Chong Dae} and Shin, {Chan Su} and Antoine Vigneron",

note = "Funding Information: ✩ Work by the first three authors was supported by the Brain Korea 21 Project, The School of Information Technology, KAIST, in 2005. Work by the fourth author was supported by the Hankuk University of Foreign Studies Research Fund of 2005. Work by the fifth author was supported by the National University of Singapore under grant R-252-000-166-112. * Corresponding author. E-mail addresses: heekap@gmail.com (H.-K. Ahn), otfried@kaist.ac.kr (O. Cheong), cdpark@jupiter.kaist.ac.kr (C.-D. Park), cssin@hufs.ac.kr (C.-S. Shin), antoine.vigneron@jouy.inra.fr (A. Vigneron).; 21st Annual Symposium on Computational Geometry, SCG'05 ; Conference date: 06-06-2005 Through 08-06-2005",

year = "2005",

doi = "10.1145/1064092.1064146",

language = "English (US)",

pages = "356--363",

}

TY - CONF

T1 - Maximizing the overlap of two planar convex sets under rigid motions

AU - Ahn, Hee Kap

AU - Cheong, Otfried

AU - Park, Chong Dae

AU - Shin, Chan Su

AU - Vigneron, Antoine

N1 - Funding Information: ✩ Work by the first three authors was supported by the Brain Korea 21 Project, The School of Information Technology, KAIST, in 2005. Work by the fourth author was supported by the Hankuk University of Foreign Studies Research Fund of 2005. Work by the fifth author was supported by the National University of Singapore under grant R-252-000-166-112. * Corresponding author. E-mail addresses: heekap@gmail.com (H.-K. Ahn), otfried@kaist.ac.kr (O. Cheong), cdpark@jupiter.kaist.ac.kr (C.-D. Park), cssin@hufs.ac.kr (C.-S. Shin), antoine.vigneron@jouy.inra.fr (A. Vigneron).

PY - 2005

Y1 - 2005

N2 - Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any ε > 0, we compute a rigid motion such that the area of overlap is at least 1 -ε times the maximum possible overlap. Our algorithm uses O(l/ε) extreme point and line intersection queries on P and Q, plus O((1/ε2)log(1/ε)) running time. If only translations are allowed, the extra running time reduces to O((1/ε) log(1/ε)). If P and Q are convex polygons with n vertices in total, the total running time is O((1/ε) logn+(1/ε2) log(1/ε)) for rigid motions and O((1/ε) log n + (1/ε) log(1/ε)) for translations.

AB - Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any ε > 0, we compute a rigid motion such that the area of overlap is at least 1 -ε times the maximum possible overlap. Our algorithm uses O(l/ε) extreme point and line intersection queries on P and Q, plus O((1/ε2)log(1/ε)) running time. If only translations are allowed, the extra running time reduces to O((1/ε) log(1/ε)). If P and Q are convex polygons with n vertices in total, the total running time is O((1/ε) logn+(1/ε2) log(1/ε)) for rigid motions and O((1/ε) log n + (1/ε) log(1/ε)) for translations.

KW - Approximation algorithm

KW - Convex shape

KW - Pattern matching

KW - Sublinear algorithm

UR - http://www.scopus.com/inward/record.url?scp=33244493774&partnerID=8YFLogxK

U2 - 10.1145/1064092.1064146

DO - 10.1145/1064092.1064146

M3 - Paper

AN - SCOPUS:33244493774

SP - 356

EP - 363

T2 - 21st Annual Symposium on Computational Geometry, SCG'05

Y2 - 6 June 2005 through 8 June 2005

ER -

Maximizing the overlap of two planar convex sets under rigid motions

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this