Publication:

Optimal Point Removal in Closed-2pm Labeling



Authors:

Farshad Rostamabadi, Iman Sadeghi, Mohammad Ghodsi, Ramtin Khosravi

Sharif Univeristy of Technology


Venue:

Information Processing Letters, January 2008

Abstract:

An optimal labeling where labels are disjoint axis-parallel equal-size squares is called 2PM labeling if the labels have maximum length each attached to its corresponding point on the middle of one of its horizontal edges. In a closed-2PM labeling, no two edges of labels containing points should intersect. Removing one point and its label, makes free room for its adjacent labels and may cause a global label expansion. In this paper, we construct several data structures in the preprocessing stage, so that any point removal event is handled efficiently. We present an algorithm which decides in O(lgn) amortized time whether a label removal leads to label expansion in which case a new optimal labeling for the remaining points is generated in O(n) amortized time.


Resources:

Publication
pdf
20 Mb
Science Direct
Science Direct

ACM Digital Library
ACM


Discussion:

Text Reference:

Farshad Rostamabadi, Iman Sadeghi, Mohammad Ghodsi, Ramtin Khosravi. Optimal point removal in closed-2PM labeling. Information Processing Letters, Volume 105, Issue 3, 31 January 2008, Pages 108-113

BibTex Reference:


@article{Rostamabadi2008optimal2pm,
	author = {Rostamabadi, Farshad and Sadeghi, Iman and Ghodsi, Mohammad and Khosravi, Ramtin},
	title = {Optimal point removal in closed-2PM labeling},
	journal = {Information Processing Letters},
	volume = {105},
	number = {3},
	month = jan,
	year = {2008},
	pages = {108--113},
}
			

Get in touch

Contact

Email

sadeghi[@]gmail[.]com


Social Network



Support


Your message was sent successfully! I will be in touch as soon as I can.

Something went wrong, try refreshing and submitting the form again.