NDLI: Labeling circular focus regions based on a tractable case of maximum weight independent set of rectangles

Please wait, while we are loading the content...

A practical approach to generating route sketches

Labeling circular focus regions based on a tractable case of maximum weight independent set of rectangles

An exploratory visualization tool for mapping the relationships between animal movement and the environment

Navigation using special buildings as signposts

Matching labels and markers in historical maps: an algorithm with interactive postprocessing

An interaction framework for level-of-abstraction visualization of 3D geovirtual environments

Interactively exploring geotemporal relationships in demographic data via stretch projections

Labeling circular focus regions based on a tractable case of maximum weight independent set of rectangles

Content Provider	ACM Digital Library
Author	Haunert, Jan-Henrik Hermes, Tobias
Abstract	We introduce a new model for labeling point features in a circular focus region that a user can define in a map. In this model, each label is an axis-aligned rectangle that touches the boundary of the focus region with one of its corners. A straight-line segment (the leader of the label) connects that corner with the corresponding point feature to ensure a clear graphical association. We require that every leader points towards the center of the focus region, which improves legibility and, in particular, avoids intersecting leaders. Our model allows only one possible position for each label. Consequently, but also more generally due to limited map space, labeling all points without overlapping labels can easily become impossible. Therefore, we compute a conflict-free labeling with the maximal number of labels or with the maximal total weight, where the weight of each label corresponds to the importance of its corresponding point. Our problems are special cases of the NP-hard problem Maximum Weight Independent Set of Rectangles (MWISR). We show that MWISR can be solved efficiently if the upper-left corners of all rectangles (of potentially different heights) lie on a monotonically ascending curve. This allows us to compute optimal labelings efficiently, e.g., in O(n log n) time for unit-height labels. We achieve a real-time performance with an implementation in JavaScript that runs in a browser.
Starting Page	15
Ending Page	21
Page Count	7
File Format	PDF
ISBN	9781450331418
DOI	10.1145/2677068.2677069
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-11-04
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Information visualization Map labeling
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in